GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 19

Question

Mark all the context-free languages given below

• A. $L = \{x\#w \mid x,w \in \Sigma^* \text{ and } x \text{ is a substring of } w\}$
• B. $L=\{a^nb^{n+m}c^md^{n}\mid n,m \geq 0\}$
• C. $L = \{1^n \mid n\text{ is a power of }2\}$
• D. $L = \{0^n1^m0^m1^n\mid m,n \geq 0\}$

Comments

@Deepak Poonia sir PDA can do mismatching so option A should be true, pls confirm

Answer 1

A is not context-free as this requires string comparison and thus an LBA.

B is not context free as we cant design a PDA here. We can solve it easily by putting $m=0$ and we get $a^nb^nc^n$ which is a well known non CFL.

C is not context-free as checking for a power of $2$ is above the limits of a PDA.

D is context-free as we can Push n 0's, followed by m 1's. Now, when 0 comes, we start popping and continue  when 1 comes (when 1 comes stack must pop 1 and not 0) also. We accept on stack being empty.

So, correct option is D.

Comments

ijnuhb 1 belongs to the alphabet set.

---

For option (A), can we have an NPDA like this –

1. push all input characters on stack till # is encountered
2. read next input. if it doesn’t match the top of the stack, repeat step 2. If it matches, non-deterministically decide whether to repeat step 2 or pop the top off the stack and go to step 3.
3. read next input, match with top of stock and pop the top off the stack if it matches. If it doesn’t match, reject. If stack is non-empty and input has finished, reject it. If stack is empty, go to step 4. else, repeat step 3.
4. if input has finished, accept it. If input has not finished, read remaining input and then accept.

What am I missing here? Is the magical non-determinism in step 2 not allowed in NPDA or something else?

---

The issue wih this approach is that it checks whether x is a substring of $w^{R}$ not w as the string is in reverse order in the stack