edited by
15,124 views
51 votes
51 votes

Let

$L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$,

$L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and

$L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $.  

Which of these languages are NOT context free? 

  1. $L_1$ only
  2. $L_3$ only
  3. $L_1$ and $L_2$
  4. $L_2$ and $L_3$
edited by

6 Answers

Best answer
68 votes
68 votes

Answer is (D)

$L_1$ is context-free. We count the number of $0$'s and check if the remaining number of $1$'s followed by 0's count to the initial number of $0$'s.

$L_2$ is not context-free. Here the number of $0$'s and the following $1$'s must be same, which can be checked using a PDA. But after that we must also ensure that the following number of $0$'s must be less than the previous count of $0$'s and $1$'s (otherwise $n < 0$, which violates the condition for acceptance) and we cannot do these two checks using a single PDA.

$L_3$ is again not context-free as it is nothing but equal number of $0$'s followed by equal number of $1$'s followed by equal number of $0$'s.

edited by
12 votes
12 votes

Take language one by one:

  1. L1 is CFL Even DCFL since push all 1's , when first 0 come start pop untill stack is empty.Take language one by one:
  2. L3 is Non -CFL Even DCFL since push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m+n since stack is empty So you need two stacks . if you took n+m=p then language look like 0^{p}1^{p}0^{p} .
  3. L2 is Non-CFL since  push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m since stack is empty So you need two stacks .
4 votes
4 votes
L1 can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L1.

But for L2 and L3 PDA implementation is not possible. The reason is, in L2 there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s.

Hence PDA implementation is not possible.

Similarly L3 also has the similar reason.
Option D is right.
2 votes
2 votes

L2 and L3 are  like  language  a^nb^nc^n. which is csl . because there is two comparision so we cannot drow PDA .

Answer:

Related questions

93 votes
93 votes
8 answers
2
Rucha Shelke asked Sep 22, 2014
33,981 views
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$