GATE CSE 2014 Set 3 | Question: 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 ...

---

$L_{1} = \{0^n1^n\;|\;n\geq 0\}$
$00001111$ in this i/p string DPDA will push $0’s$ then after seeing $1’s$ will start to pop. Hence this DCFL.

$L_{2}=\{wcw^r\;|\;w\in \{0,1\}^*\}$
$0101c1010$ in this i/p string DPDA will start pushing $0101$ then seeing $c$ skip and now start poping while matching. Hence this is DCFL.

$L_{3}=\{ww^r\;|\;w\in \{0,1\}^*\}$
$01011010$ here DCFL don’t know where to pop or push. But PDA can do this with non-determinism. So this is CFL but not DCFL.

Answer 1

Correct Option: 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.