Theory of Computation

Question

$L1= \left \{ a^m b^n c^n d^m | m \neq n \right \}$

$L2=   \left \{a^i b^j c^k | (i<=j)or (j<=i), j=k  \right \}$

$L3=  \left \{a^i b^j c^k| i=j, j<k  \right \}$

The number of the above languages that are context free are ?

Comments

If they are same then the string is not a part of $L_1$, like abcd is accepted by your PDA but should not be accepted

---

Oh thankyou so much sir.

---

i'm an aspirant too, don't call me sir :)

Answer 1

In L2

i>=j or j>=i ---> So we can ignore i value here i.e. L2={a^i b^j c^j}   .Which is context free.

But I cannot find any such way for L1 or L3.

Conclusion:

So only L2 is CFL

Comments

L3 is not CFL Because there will not be left any j to compare with k.

---

In L2 there will be the condition of aⁿbⁿcⁿ    

or not ???

When i = j and j = k.

---

Yes.

There could be such situation but it should decide anything because a^n b^m m&n >0 is regular it contains a^n b^n as well.