edited by
197 views
0 votes
0 votes
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ so that its input alphabet is $\{a, b, c\}$. When it first enters an accept state, it pretends that $c’s$ are $b’s$ in the input from that point on. What language would the modified $P$ accept?)
edited by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
1 answer
2
admin asked Oct 12, 2019
323 views
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
0 votes
0 votes
1 answer
4