Pushdown Automata and Context-Free Languages: Examples and Counterexamples

On input $aabb$, the unread-input/stack pairs may evolve as $(aabb,S)\to (aabb,aSb)\to (abb,Sb)\to (abb,aSbb)\to (bb,Sbb)\to (bb,bb)\to (b,b)\to (\epsilon ,\epsilon )\mathrm{.}$ The four input-consuming moves pop the displayed top terminal, while the three other moves expand $S$ by $aSb$, expand it once more, and finally replace it by $\epsilon$.

The same pattern works for every word $a^n{b}^n$: repeat $S\to aSb$ and immediately read and pop the new top $a$, exactly $n$ times; then use $S\to \epsilon$ and read and pop the remaining $n$ symbols $b$. Therefore the constructed PDA recognizes $\{a^n{b}^n:n\ge 0\}$.

This is the standard grammar-to-PDA construction from [L1] on a concrete language.

The displayed machine is deterministic because before the first $b$ it has only the unique push move on $a$, after the first $b$ it has only the unique pop move on $b$, and the endmarker is accepted only when the stack has returned to the bottom marker. Therefore it recognizes exactly $\{a^n{b}^n:n\ge 0\}$.

The grammar $S\to aSb\mid \epsilon$ generates the same language and has exactly one derivation for each word $a^n{b}^n$, because the number of leading $a$'s uniquely determines how many times the recursive rule must be used before the final $\epsilon$ step.

So this language is deterministic context-free, and [L2] is realized concretely by an unambiguous grammar.

The original machine recognizes $\mathrm{\varnothing }$, because it loops forever on every marked input. After swapping the accepting status of its only state, the machine still has exactly the same infinite computation on every marked input and still recognizes $\mathrm{\varnothing }$.

But the complement of $\mathrm{\varnothing }$ is the full language ${\mathrm{\Sigma }}^{\ast }$, so the swapped machine does not recognize the complement of the original language.

Therefore this looping DPDA is a counterexample to [A1].