Pushdown Automata and Context-Free Languages

For final-state to empty-stack, adjoin a fresh bottom marker $B$ below the original stack and a fresh drain state $d$. Whenever the simulated machine reaches an accepting state after consuming all input, the new machine takes an $\epsilon$-move to $d$ and in state $d$ repeatedly pops the entire remaining stack, including $B$. By [L1] and [L2], the new machine accepts exactly the same words, now by empty stack.

For empty-stack to final-state, adjoin a fresh start state $s$, a fresh bottom marker $B$, and a fresh accepting state $f$. The new machine first pushes the old initial symbol above $B$, then simulates $M$, and the only way to enter $f$ is by an $\epsilon$-move that pops $B$ after the simulated stack has become empty and the input has been fully consumed. By [L1] and [L2], this converts empty-stack acceptance into equivalent final-state acceptance.

The two constructions from steps 1.1 and 1.2 prove both directions of the equivalence.

Define a one-state PDA $M_G$ whose initial stack symbol is $S$. If the top stack symbol is a variable $A$ and $A\to \alpha$ is a production of $G$, the machine has an $\epsilon$-move replacing $A$ by $\alpha$; if the top stack symbol is a terminal $a$, the machine may read an input symbol $a$ and pop it.

Every leftmost derivation of a word $w$ in $G$ yields an accepting computation of $M_G$: keep the current sentential form on the stack, use the step from 1.1 to expand its leftmost variable exactly as the derivation does, and then match terminals against the input once only terminals remain on top. Therefore [L1], [L2], and [L3] give $L(G)\subseteq N(M_G)$.

Conversely, every accepting computation of $M_G$ determines a leftmost derivation in $G$, because the only $\epsilon$-moves replace the current top variable by the right-hand side of one production and the only input-consuming moves match the current top terminal against the next input symbol. Reading those stack-replacement moves in order reconstructs a leftmost derivation of the accepted word. Hence $N(M_G)\subseteq L(G)$.

Steps 2.1 and 2.2 prove $N(M_G)=L(G)$.

Assume $x\in [p,Z,r]$ and $y\in [r,Y,q]$, and let $\alpha$ be any stack suffix. Then [L1] gives $(p,x,ZY\alpha ){⊢}_M^{\ast }(r,\epsilon ,Y\alpha )$ and also $(r,y,Y\alpha ){⊢}_M^{\ast }(q,\epsilon ,\alpha )$. Concatenating these two computations yields $(p,xy,ZY\alpha ){⊢}_M^{\ast }(q,\epsilon ,\alpha )$.

Conversely, let $(q,v,\alpha )$ be the first configuration with stack $\alpha$ in a computation starting at $(p,w,ZY\alpha )$. Before that point there is a first configuration whose stack is $Y\alpha$; write it as $(r,yv,Y\alpha )$ and write $w=xyv$, where $x$ is the input prefix consumed before it is reached and $y$ is consumed between the two first-exposure configurations. The computation therefore contains $(p,xyv,ZY\alpha ){⊢}_M^{\ast }(r,yv,Y\alpha ){⊢}_M^{\ast }(q,v,\alpha )$. Neither segment inspects the suffix $\alpha$ before its endpoint. Hence the same transition sequences work above every stack suffix $\beta$, giving $(p,x,Z\beta ){⊢}_M^{\ast }(r,\epsilon ,\beta )$ and $(r,y,Y\beta ){⊢}_M^{\ast }(q,\epsilon ,\beta )$. By [L1], $x\in [p,Z,r]$ and $y\in [r,Y,q]$.

Therefore fragment computations compose exactly by concatenating the consumed words and, conversely, by splitting at the first moment when the lower stacked symbol is exposed.

By [L1], replace $M$ by an equivalent empty-stack PDA $M^{\mathrm{\prime }}$. Refining its transitions if necessary, we may assume that every move of $M^{\mathrm{\prime }}$ pops one symbol, reads either one input symbol or $\epsilon$, and pushes either nothing, one symbol, or two symbols; a longer push is replaced by a short chain of fresh intermediate states.

Build a grammar $G_M$ whose variables are the fragment symbols $[p,Z,q]$ for states $p,q$ and stack symbols $Z$, and whose start symbol branches over all variables $[q_0,Z_0,q]$. For each normalized transition $(r,\beta )\in \delta (p,a,Z)$ of $M^{\mathrm{\prime }}$ with $a\in \mathrm{\Sigma }\cup \{\epsilon \}$, add the matching productions: if $\beta =\epsilon$, add $[p,Z,r]\to a$; if $\beta =Y$, add $[p,Z,q]\to a[r,Y,q]$ for every state $q$; if $\beta =YW$, add $[p,Z,t]\to a[r,Y,s][s,W,t]$ for every pair of states $s,t$. When $a=\epsilon$, omit that leading terminal.

Every derivation in $G_M$ yields an accepting computation of $M^{\mathrm{\prime }}$ by induction on the derivation tree of a fragment variable $[p,Z,q]$. The production chosen at the root records the first normalized move from state $p$ with top symbol $Z$. If the production is terminal or $\epsilon$, that move already removes $Z$. If it has one fragment variable, the induction hypothesis supplies the computation removing the pushed symbol. If it has two fragment variables, the induction hypotheses supply computations removing the two pushed symbols, and [L3] composes them into one computation removing the original pushed pair. Therefore every word derived from $[p,Z,q]$ lies in that fragment language, and the start productions give $L(G_M)\subseteq N(M^{\mathrm{\prime }})$.

Conversely, consider a fragment computation $(p,w,Z\alpha ){⊢}_{M^{\mathrm{\prime }}}^{\ast }(q,\epsilon ,\alpha )$ and induct on its number of steps. Let its first normalized move be determined by a transition $(r,\beta )\in \delta (p,a,Z)$ with $a\in \mathrm{\Sigma }\cup \{\epsilon \}$ and $\beta \in \{\epsilon ,Y,YW\}$. If $\beta =\epsilon$, that one move already removes $Z$, so step 2.1 contributes the corresponding terminal or $\epsilon$ production. If $\beta =Y$, the remaining computation removes $Y$ above $\alpha$, so the induction hypothesis derives the remaining input from $[r,Y,q]$, and step 2.1 prepends the production $[p,Z,q]\to a[r,Y,q]$ with the leading terminal omitted when $a=\epsilon$. If $\beta =YW$, then [L3] splits the remaining computation at the first moment when $W$ is exposed on top of $\alpha$, yielding a state $s$ and a decomposition of the remaining input into words $u$ and $v$ with $(r,u,YW\alpha ){⊢}_{M^{\mathrm{\prime }}}^{\ast }(s,v,W\alpha )$ and $(s,v,W\alpha ){⊢}_{M^{\mathrm{\prime }}}^{\ast }(q,\epsilon ,\alpha )$. The induction hypothesis derives $u$ from $[r,Y,s]$ and $v$ from $[s,W,q]$, so step 2.1 gives a derivation of $w$ from $[p,Z,q]$. Applying this to start configurations shows $N(M^{\mathrm{\prime }})\subseteq L(G_M)$.

Steps 3.1 and 3.2 give $L(G_M)=N(M^{\mathrm{\prime }})$, and [L1] then yields $L(G_M)=T(M)$.

If $L$ is context-free, choose a grammar generating $L$. Then [L1] gives a PDA recognizing the same language.

If some PDA recognizes $L$, then [L2] gives a context-free grammar generating that same language.

Therefore $L$ is context-free if and only if some PDA recognizes it.

From any configuration of $M$, the pair consisting of the current state and top stack symbol determines at most one legal next step by [L1].

Therefore two computations on the same input and with the same initial configuration must agree on their first move whenever either has a first move. Repeating the same argument after each common prefix shows inductively that they agree step by step for as long as both are defined.

Thus any two finite computations from the initial configuration are comparable by extension. Their union, when the computation continues indefinitely, or their common terminal extension, when it halts, is the unique maximal computation on $w⊣$.

In the grammar $G_M$, every production choice records one concrete local decision in an accepting computation of $M$: either one normalized PDA move, or one split state used to divide a two-symbol fragment into two smaller fragments. Thus a leftmost derivation of a word in $G_M$ determines an accepting computation of $M$ on that word.

Conversely, the accepting computation of a word determines all of those local choices uniquely, because the first moment when each top stack symbol disappears fixes the fragment split and therefore fixes the next production in the fragment-variable grammar. So one accepting computation determines exactly one leftmost derivation in $G_M$.

If some generated word had two different leftmost derivations in $G_M$, steps 1.1 and 2.1 would yield two different accepting computations of $M$ on that word, contradicting the hypothesis. Therefore [L1] shows that $G_M$ is unambiguous.

Choose a DPDA $M$ recognizing $L$ by [L1].

Form an equivalent DPDA $\widehat{M}$ that records whether the endmarker has been consumed. Before $⊣$ it simulates $M$ in a pre-endmarker copy of the state set; a transition consuming $⊣$ enters the post-endmarker copy; and all subsequent $\epsilon$-moves remain in that copy. Declare a post-endmarker copy accepting exactly when its underlying state lies in $F$, and delete every outgoing move from those accepting copies. This preserves determinism by [L1]: it only duplicates states and removes moves.

The machine $\widehat{M}$ recognizes the same language as $M$. Indeed, an accepting computation of $M$ has consumed the marked input and hence reaches a post-endmarker accepting copy in $\widehat{M}$; conversely, every accepting copy projects to an accepting configuration of $M$. Halting at the first such copy does not change whether that configuration is reachable.

Every accepting computation of $\widehat{M}$ is maximal because its accepting states have no outgoing moves. By [L2], there is therefore at most one accepting computation on each marked input.

Applying [L3] to $\widehat{M}$ yields an unambiguous context-free grammar generating its language, which is $L$ by step 3.1. Therefore every deterministic context-free language is unambiguous.

Choose a DPDA $M$ recognizing $L$ by [L1].

Apply the complementation construction from [F1] to $M$. It produces a DPDA $M^c$ over the same alphabet that accepts exactly the marked words $w⊣$ not accepted by $M$.

Because $M^c$ recognizes exactly the marked complement of the language of $M$, it recognizes ${\mathrm{\Sigma }}^{\ast }\setminus L$. Therefore ${\mathrm{\Sigma }}^{\ast }\setminus L$ is deterministic context-free.

The displayed machine recognizes the empty language, because on every marked input it follows the unique $\epsilon$-loop forever and never reaches an accepting final state.

If we merely declare the state $q$ to be accepting, the machine still follows exactly the same infinite $\epsilon$-loop on every marked input, so it still recognizes the empty language. In particular, it does not recognize the complement ${\mathrm{\Sigma }}^{\ast }$.

This contradicts [A1]. The complement theorem [L2] needs the endmarker and loop repairs; naive state swapping does not suffice.

In the displayed PDA, the empty word is accepted by final state in zero moves because the start state is accepting.

The same machine does not accept the empty word by empty stack, because the stack begins with $Z_0$ and there is no transition that removes it. So the required empty-stack configuration never occurs.

Thus the two acceptance notions differ on this fixed machine, contradicting [A1]. The correct general statement is the language-class equivalence from [L3].