recategorized by
665 views
2 votes
2 votes

Which of the following languages are not CFLs

  1. $L=\{ 0^n 1^n0^n 1^n \mid n \geq 0\}$
  2. $L=\{0 \# 0^{2n} \# 0^{3n} \mid n \geq 0\}$
  3. $L=\{a^n b^m c^m d^n \mid m,n \geq 0\}$
  4. $L=\{ x \# y \mid x,y \in \{0, 1\}^* \text{ and } x \neq y\}$

 

  1. II and III only
  2. III and IV only
  3. I and II only
  4. I, II and IV only
recategorized by

1 Answer

1 votes
1 votes
I. Requires more than one memory element to accept the given $L$ Non-CFL
II. Requires more than one memory element to accept the given $L$ Non-CFL
III. The given Language Accepted by one-Stack PDA
Let $m=2, \: n=1$
Then $w=abbccd$
Push all a's and b's  in to the stack and for every c pop one b from stack and for every d pop a from stack. After processing the complete input stack is empty and is accepted by PDA. So that the given language is CFL.
IV. The given Language Accepted by one-Stack PDA,CFL.
I and II are not CFLs.
Answer:

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
1 answer
4