edited by
9,758 views
32 votes
32 votes

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?

  1. None of the languages
  2. Only $L_1$
  3. Only $L_1$ and $L_2$
  4. All the three languages
edited by

2 Answers

Best answer
44 votes
44 votes

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. 

edited by
2 votes
2 votes

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

Answer:

Related questions

45 votes
45 votes
7 answers
4