GATE2014-3-36

Question

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$

$L_1  = \left\{0^n1^n\mid n \geq 0\right\}$

$L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$

$L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$

Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic Context-free languages?

• A. None of the languages
• B. Only $L_1$
• C. Only $L_1$ and $L_2$
• D. All the three languages

Comments

L₃ is Non deterministic CFL ...

Answer 1

C.

$L_3$  is CFL and not DCFL as in no way we can deterministically determine the MIDDLE point of the input string. 

Comments

Should not the answer be B? Because c belongs to the input alphabet.

---

As c belongs to the input alphabet, it is used to determine the middle part of the string.
for example 110c011 is in the language L₂. every element is pushed to the stack untill a c occurs. Then the pda changes state and the popping starts.

---

Oh yea. Sorry. I mistook c to be a part of w as well.

---

If your push and pop is clear then it  is deterministic context free language otherwise not.

Answer 2

For the languages L₁ & L₂   we can have deterministic push down automata, so they are
DCFL’s, but for L₃ only non-deterministic PDA possible. So the language L₃ is not a
deterministic CFL.

Answer 3

L1 and L2 are deterministic CFL, as we can design DPDA for them.

But in L3, we cannot make DPDA for it, as we cannot locate the middle of the string, so DPDA for L3 is not possible. It can be accepted by only NPDA, so L3 is CFL but not DCFL.