in Theory of Computation edited by
735 views
4 votes
4 votes
suppose we define max(L) = $ \{ \; x \;|\; x \in L,(\;\forall y \in \Sigma ^*,(y\neq \lambda )\Rightarrow (xy\notin L)\;\;) \;\}$

let L$_1$ = $ \{ \;a^ib^jc^k\;|\;k ≤i \;or\; k ≤j;where\; i,j,k ≥ 0 \;\}$ and  L$_2$ = $ \{ \;a^ib^jc^k\;|\;i,j,k ≥ 0 \;\}$

then which of the following statement is correct?

(a) max( L$_1$ ) and max( L$_2$ ) are not CFL.

(b) max( L$_1$ ) and max( L$_2$ ) are CFL

(c) max( L$_1$ ) is CFL but max(  L$_2$ ) is not CFL.

(d) max( L$_2$ ) is CFL but max( L$_1$ ) is not CFL.
in Theory of Computation edited by
735 views

4 Comments

Shaik brother can you see here i tried the same as u told but nothing is happening https://gateoverflow.in/269840/gate-zeal-test-toc
0
0
you close it ( simultaneously two people can't edit, ), i will check it!
0
0

Shaik brother can you see here i tried the same as u told but nothing is happening

don't give space between \ and ; for getting space in our text,

don't give space between \ and { for getting { in our text,

0
0

1 Answer

4 votes
4 votes
Best answer

Answer : D

Let's analyze each language one by one.

1. $max(L) :$ Informally, and in simple words,   $max(L)$ is just a subset of strings of $L$ such that those strings are maximal i.e. those strings cannot be appended with anything. i.e. If $w$ is a string in $L$ then it will be in $max(L)$ if and only if $wx$ is Not in $L$ for any(all) $x$ such that $|x| \geq 1$


2. $L1 = $ $\left \{ a^ib^jc^k| k \leq i \,\, or\,\,k\leq j; i,j,k \geq 0 \right \}$ 

$L1$ consists of the Union of the following languages : $a^*,b^*,a^*b^*,$ $a^{\geq m} b^nc^m$ and $a^n b^{\geq m}c^m \,\,such \,\,that \,\,m\geq 1$ 

Now, If you analyze each of the sublanguages of $L1, $ You can always append something to $a^*$ (append one more $a$), You can always append something to $b^*$ (append one more $b$), You can always append something to $a^*b^*$ (append one more $b$). 

Coming to last two sublanguages i.e. $a^{\geq m} b^nc^m$ and $a^n b^{\geq m}c^m \,\,such \,\,that \,\,m\geq 1,$ You can only append $c's$ to the strings of these languages, that too only when $\#(c)$ is strictly less than $max(\#(a), \#(b)). $ (Try, check and see)

So, we can say that the maximal strings of $L1$ are of the form $a^m b^nc^m, such\,\,\, that\,\,\, n\leq m$ Or $a^n b^m c^m, such\,\,\, that\,\,\, n\leq m \,\,;Where \,\,m\geq 1$  

Hence, $max(L1) = $ $\left \{ a^mb^nc^m| n\leq m, m \geq 1 \right \}$   $\cup$  $\left \{ a^nb^mc^m| n\leq m, m \geq 1 \right \}$

Now, It is easy to see that $max(L1) $ is Non-CFL ( Because Two comparison conditions).


3. $L2 = $  $\left \{ a^ib^jc^k|  i,j,k \geq 0 \right \}$ 

$Max(L2)$ is empty language because You can always append something at end of every string in $L2$ (Hint : Just append the last symbol of $w$ at the end of $w$ )

Hence, $max(L2)$ is Empty, Hence, Regular, hence, CFL.


One thing to Note from $max(L1)$ is  That "set of $CFL's$ is Not closed under $max$ Operation."

selected by

4 Comments

@Deepakk Poonia (Dee)

Sorry some error for my prev comment

Check in this question https://gateoverflow.in/3570/gate2006-it-31

there

$\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$. is NCFL

there also more than one comparison

Now, here in this question

max(L1) can also be like this

right?

Why r u taking

max(L1)=$a^{n}b^{n}c^{n}$? 

0
0

See this toohttps://gateoverflow.in/179295/tifr2018-b-11

union of two CFL can be CFL too

0
0
max(L1)  can be $a^{n+2}.b^{m}.c^{n+2}$

right?
0
0

Related questions