303 views
0 votes
0 votes
The proof of Lemma $2.41$ says that $(q, x)$ is a looping situation for a $DPDA \:P$ if when $P$ is started in state $q$ with $x \in \Gamma$ on the top of the stack, it never pops anything below $x$ and it never reads an input symbol. Show that $F$ is decidable, where $F = \{ \langle P, q, x \rangle \mid (q, x)\: \text{is a looping situation for P}\}$.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
4
admin asked Oct 17, 2019
252 views
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable...