#Self Doubt

Question

L = {0^n 1^2n 0^n+m , n,m>=0}

Is this Language CFL or non CFL?

According to me

1. we can write this as 0^n 1^n 1^n 0^n 0^m
2. Then we will keep on pushing 0’s and as and when we get 1 we keep on popping 0’s, now once the stack is empty and input is 1 we keep on pushing 1 and again as and when we get 0’s as input we keep on popping 1 till the stack is empty and then on seeing any number of 0’s we don’t push anything and when we reach the end of the string we simply move to the final state.

Is this logic correct?

Comments

Yes non CFL.

---

It is non-CFL. PDA can’t do more than 2 Infinite nonlinear power comparison on the same variable.

---

Thanks @Abhrajyoti00

Answer 1

Logic seems correct. To verify whether a language is context-free, you can use the pumping lemma for context-free languages. This states that if a language is context-free, there exists a number p (the "pumping length") such that any string s in the language with length greater than p can be written as s = xyz, where |xy| <= p, |y| > 0, and for all i >= 0, xy^iz is also in the language.

If we apply the pumping lemma to the language L, we can see that it does not satisfy the conditions of the lemma. In particular, it is not possible to pump any string in L to obtain a longer string that is also in the language. Therefore, L is not a context-free language.