Dark Mode

735 views

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.

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

0

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

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