edited by
1,130 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.
edited by

1 Answer

Best answer
4 votes
4 votes

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

Related questions

2 votes
2 votes
2 answers
4