5 views
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. 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 behavior, so $P’s$ subsequent behavior can depend only on $q$ and $x$.)
| 5 views