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

0 votes
0 votes
for  the first one I can construct a grammar like this;
S->0S0|EPSILON|A
A->0A1|EPSILON
so this  is context free.

For the second one to construct it we need an npda with 2 stacks.
 Or we can argue like this that if n=0 then the resulting language becomes a^n b^n c^n which is not a cfg.

for the third one it is exactly like :
a^n b^n c^n which is not a CFG.
0 votes
0 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.
Answer:

Related questions

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