#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

It is CFL.

---

Thank you @Vishal_kumar98, I found a thread which says it is not so that is why was confused because I could write a procedure which I have mentioned above which proves the language as DCFL.

Theory of Computation: is it DCFL OR NOT? (gateoverflow.in)

Can you please check and clarify once. Thanks a lot in advance.

---

@Sunnidhya Roy

Take this string for example ,

$0^{3}1^{5}0^{2}$  from your algorithm this string will also be accepted .

First push all 0’s . now pop the stack as long as you see 1’s . now remaining 2 string push into the stack .Now you see 2 0’s and pop 2 1’s . So if you create the pda using your algorithm that will end up accepting thin kind of string as well .

 

---

I think this language is not CFL .There is no such algorithm possible .

---

Thanks a lot @Kabir5454 got my mistake, so this will be a non CFL right?

---

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.