Greibach’s Theorem

Greibach’s Theorem: There is a theorem analogous to Rice’s Theorem for PDAs. Known as Greibach’s Theorem, the high-level statement of the theorem (in terms of its practical usage) is as follows:
It is impossible to algorithmically classify (using, of course, a Turing machine) context-free grammars on the basis of whether their languages are regular or not.

The Computation History Method: As we mentioned , it is possible to “teach” LBAs (and NPDAs) to answer certain difficult questions about Turing machines. This idea is detailed in Section 17.3.2 through 17.3.4. We first recap basic facts about linear bounded automata (LBA) and present a decidability result about them (Section 17.3.1). Thereafter, we present three undecidability results based on the computation history method: (i) emptiness of LBA languages (Section 17.3.2), (ii) universality of the language of a CFG (Section 17.3.3), and (iii) Post’s correspondence problem (Section 17.3.4). In Chapter 18, Section 18.2.3, we emphasize the importance of the undecidability of Post’s correspondence problem (PCP) by presenting a classic proof due to Robert Floyd: we reduce PCP to the validity problem for first-order logic. This proof then establishes that the validity problem for first-order logic is undecidable.

Decidability of LBA acceptance: LBAs are Turing machines that are allowed to access (read or write) only that region of the input tape where the input was originally presented. To enforce such a restriction, one may place two distinguished symbols, say and , around the original input string.1 With these conventions, it can easily be seen that instantaneous descriptions of an LBA that begin as q0w will change to the general form lqr, where |lr| = |w|. Therefore, there are a finite number, say N, of these IDs (see Exercise 17.1). A decider can simulate an LBA starting from ID q0w, and see if it accepts within this many IDs; if not, the LBA will not accept its input. Hence, LBA acceptance is decidable.

Undecidability of LBA language emptiness: Suppose a Turing machine M accepts input w; it will then have an accepting computational history of IDs starting with q0w, going through intermediate IDs, and ending with an ID of the form aqf b where qf ∈ F. With respect to a given M,w pair, it is possible to generate an LBA
LB    M,w  that accepts a string s exactly when s is a sequence of IDs representing an accepting computational history of M running on w.2 All LB M,w need to do is this: check that the first ID is q0w; check that the i 1st ID follows from the ith ID through a legal transition rule of the Turing machine M; and check that the final ID is of the form aqf b. Hence, if the emptiness of an LBA’s language were decidable through a decider DE LBA, one could apply it to LB    M,w . By virtue of its design, LB    M,w has an empty language exactly when M does not accept w.
Therefore, the decision of DE LBA would be tantamount to whether or not M accepts w — a known undecidable problem; and hence, DE LBA cannot exist.

Undecidability of PDA language universality: The question of whether an NPDA over alphabet Γ has a universal language (language equal to Γ ∗) is undecidable. The proof proceeds almost exactly like the proof that DE LBA cannot exist.
• We will define an NPDA P    M,w  (created with respect to Turing machine M and input string w), such that

• The language of P    M,w is Γ∗ if M does not accept w.
• The language of P    M,w is Γ∗ \ {s} if M accepts w through an accepting computational history s.

If we manage to define such an NPDA, then simply feeding it to a claimed decider for universality will allow us to solve the acceptance problem of Turing machines, which is known to be undecidable.