[Solved]: Is it decidable whether a pushdown automata recognizes a given regular language?

Problem Detail: 

The problem whether two pushdown automata recognize the same language is undecidable. The problem whether a pushdown automata recognizes the empty language is decidable, hence it is also decidable whether it recognizes a given finite language. It is undecidable whether the language accepted by a pushdown automata is regular. But ...

... is it decidable whether a pushdown automata recognizes a given regular language?

In case the answer is no, does the problem becomes decidable if the given regular language has star height $1$?

Asked By : Thomas Klimpel

Answered By : Hendrik Jan

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet.

Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for this result to Hartmanis (1967), Context-free languages and Turing machine computations.

A convenient coding of the computations of a Turing machine $M$ is as follows. A configuration of TM $M$ is a string of the form $xpy$ where $uv$ is the contents of the tape, and the state $p$ is indicated at the postion where the head resides. It is important to note that computational steps of a TM are local changes: $ucpav \vdash uqcbv$ for the instruction $(p,a,q,b,L)$ where the head moves left, and $ucpav \vdash ucbqv$ for the instruction $(p,a,q,b,R)$ where the head moves right.

A valid computation can be coded as a string $w_0\#w_1^R\#w_2\#w_3^R\# \dots$ where $w_0 = q_0x$ codes the initial configuration on string $x$, and we have proper steps $w_i \vdash w_{i+1}$. The last configuration in the string should be final, i.e., have a halting/final state.

It is now an exercise to verify that the strings that are not valid computations can be generated by a CFG $G_M$ (or accepted by a PDA). The strings that do not consist of configuration sequences are even regular. Otherwise one non-deterministically guesses a position where not $w_i \vdash w_{i+1}$. This part of the string is generated by a grammar that is similar to one for $\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$.

If the TM $M$ has no accepted strings, it will have no valid computations, and all strings are generated by the grammar $G_M$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41822