Applied Course | Mock GATE | Test 1 | Question: 52

Question

Which of the following languages are not CFLs

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

 

• A. II and III only
• B. III and IV only
• C. I and II only
• D. I, II and IV only

Comments

$I$ isn't CFL since we can do "push,pop,push,pop"; but we'd never know if the latter number of <push,pop> were equal to the former one.

 

$II$ isn't CFL. Three simultaneous comparisons is a classic CSL example.

 

$III$ is CFL. Push, push, pop, pop.

 

$IV$ There's a typo in the question. It should be $|x|\neq |y|$. It is CFL.
http://www.ccs.neu.edu/home/viola/classes/slides/slides-context-free.pdf

Answer 1

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.

Comments

IV is also not a CFL.

How can it be a CFL?

---

yes..IV is not cfl, if the language is L={x#y∣x,y∈{0,1}∗ and x≠y}L={x#y∣x,y∈{0,1}∗ and xR≠y} then it would have been cfl. comparing reverse of the string could have be done 

---

For L4

https://cs.stackexchange.com/questions/307/show-that-xy-%E2%88%A3-x-y-x-%E2%89%A0-y-is-context-free

---

In the given question, |x| need not be equal to |y|.