Question

Consider the following languages
$L_1$={$w{w}^R$ | $w\in$ ${(0,1)}^{\ast }$}
$L_2$={$w\ne w^R$ | $w\in$ ${(0,1)}^{\ast }$} where $\ne$ is a special symbol
$L_3$={$ww$ | $w\in$ ${(0,1)}^{\ast }$}
Which one of the following is TRUE?

• A. $L_3$ is a CFL, but not a deterministic CFL
• B. $L_3$ is a deterministic CFL
• C. $L_1$ is a deterministic CFL
• D. $L_2$ is a deterministic CFL

Answer 1

The correct option is D $L_2$ is a deterministic CFL

$L_1$ is CFL but not a DCFL, since accepting $w{w}^R$ necessarily involves finding the middle of the string, which involves non-determinism.
$\therefore$ (a) is false.
$L_2$ is a DCFL is true since "$\ne$" is a special symbol and middle of string can now be surely found by using "$\ne$", thereby eliminating the need for non-deterministic guessing. So (b) is true.
$L_3$ is a CSL and not a CFL. So (c) is false.
$L_3$ is not a DCFL either. So (d) is false.