274 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.$

Please log in or register to answer this question.

Related questions

2 votes
2 votes
0 answers
2
admin asked Apr 7, 2019
440 views
Give deterministic pushdown automata to accept the following languages$:$$\{0^{n}1^{m}|n\leq m\}$$\{0^{n}1^{m}|n\geq m\}$$\text{\{$0^{n}1^{m}0^{n}$|n and m are arbitrary\...