Question

Let C=$\left\{W{W}^R\overline{)W\in \left\{0,1\right\}*}\right\}.$. Prove that C is not a DCFL. (Hint: Suppose that when some DPDA P is started in state q with symbol x on the top of its stack, P never pops its stack below x, no matter what input string P reads from that point on. In that case, the contents of P’s stack at that point cannot affect its subsequent behaviour, so P’s subsequent behavior can depend only on q and x).

Short answer

It can be proved that C is not a deterministic Context-free Language.

Step-by-step solution

Explain DCFL.

Deterministic Context Free Languages are accepted by the deterministic pushdown automata. DCFL is an unambiguous and accept an unambiguous grammar. Deterministic Pushdown Automata is used to recognizes the DCFL.

Prove that C is not a DCFL.

Consider the given language,$C=\left\{W{W}^R\overline{)W\in \left\{0,1\right\}*}\right\}$, the transition of the language is as follows,

State	Transition function	Current State
$q_0$	$\left(0,z0,0z0\right)$	$q_1$
$q_0$	$\left(1,z0,1z0\right)$	$q_1$
$q_1$	$\left(0,0,00\right)$	$q_1$
$q_1$	$\left(0,1,01\right)$	$q_1$
$q_1$	$\left(0,0,\in \right)$	$q_1$
$q_1$	$\left(1,1,11\right)$	$q_1$
$q_1$	$\left(1,0,10\right)$	$q_1$
$q_1$	$\left(1,1,\in \right)$	$q_1$
$q_1$	$\left(\in ,z0,z0\right)$	$q_2$

The transition function in the above table is defined as,$\delta \left(input,stack,string\right)$ .

The above pushdown automata is designed to recognize the language C .

The given PDA provides the non-deterministic selection assuming not being at a midpoint, and being a midpoint.

Therefore, from the above discussion it can be concluded that the language given is not a deterministic context free language.