735 views
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.

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
you close it ( simultaneously two people can't edit, ), i will check it!

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,

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."

@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}$?

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

union of two CFL can be CFL too

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

right?

1 vote