in Theory of Computation
275 views
0 votes
0 votes
Show that the language

   $L=\{0^{n}1^{n}|n\geq 1\}\cup \{0^{n}1^{2n}|n\geq 1\}$

is a context-free language that is not accepted by any $DPDA$ Hint$:$ Show that there must be two strings of the form $0^{n}1^{n}$ for different values of $n,$ say $n_{1}$ and $n_{2}$ that cause a hypothetical $DPDA$ for $L$ to enter the same $ID$ after reading both strings. Intuitively the $DPDA$ must erase from its stack almost everything it placed there on reading the $0's,$ in order to check that it has seen the same number of $1'.$  Thus the $DPDA$ cannot tell whether or not to accept next after seeing $n_{1}$ $1's$ or after seeing $n_{2}$ $1's.$
in Theory of Computation
by
275 views

1 comment

??
0
0

Please log in or register to answer this question.

Related questions