Question

Let INFINITE PDA = {<M>|M is a PDA and L(M) is an infinite language}. Show that INFINITE PDA is decidable.

Answer 1

Let INFINITE PDA = {<M>|M is a PDA and L(M) is an infinite language}.

--> Build a turing machine that will do the following .

--> Read <M> and create an equivalent context-free grammar G.

--> Convert G to Chomsky Normal Form. Call it G'

--> Do a breadth-first search of the grammar rules of G' looking for recursion

--> That is, does there exist a derivation A ⇒ uAv?

--> If so, then accept <M>

--> If not, then reject <M>