16
$\begingroup$

The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton 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 automaton is regular. But ...

... is it decidable whether a pushdown automaton 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$?

$\endgroup$
  • 1
    $\begingroup$ Note that equivalence of deterministic PDAs is decidable. $\endgroup$ – sdcvvc Apr 25 '15 at 21:42
14
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ There's a proof in Section 17.3.3 of Computation Engineering: Applied Automata Theory and Logic by Ganesh Gopalakrishnan $\endgroup$ – Pål GD Apr 25 '15 at 10:53
  • 2
    $\begingroup$ Note that $\Sigma^*$ is even star-free (via $\overline{\emptyset}$) so there is no hope there either. $\endgroup$ – Raphael Apr 28 '15 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.