A finite automaton can remember whether it has seen a delimiter, but its finite state alone cannot count an unbounded number of opening symbols. A pushdown automaton (PDA) adds a stack. The useful question is not merely “what should it push?” but what statement does the stack certify after every step? An invariant turns a plausible trace into a proof about every input length.
We first recognize two equal blocks, where the change from a to b reveals the matching point. Then we recognize even palindromes without a delimiter. There the machine may have to guess where its pushing phase ends. We will keep the distinction between one failed guess and rejection of the whole input explicit.
Conventions: configurations and acceptance
Definition 9.1.1
(What a configuration records)
Write a configuration as , consisting of the current state, the unread input and the stack. We write the top of the stack on the left. The bottom marker starts on the stack and our machines never pop it.
A transition may consume one input symbol or consume (no input). It can inspect the top stack symbol and replace that top by a finite string. For example, replacing by pushes ; replacing by pops it.
We use final-state acceptance with all input consumed: a word is accepted if at least one finite run reaches a final state with no unread input. Reaching a final state while input remains does not accept that word. An unavailable transition simply ends that run. In a nondeterministic machine, the word is rejected only when no accepting run exists.
These are conventions for the machines below, not a claim that every textbook writes stacks in this order or uses the same acceptance convention. A stack is potentially unbounded, but each particular finite run uses only finitely many cells.
Equal blocks: let the stack measure the unmatched prefix
Let
Use a pushing state , a matching state and a final state . Initially the machine is in . The following table lists all transitions; a blank case has no transition. In a row, stands for either or .
| State | Input consumed | Top | New state | Replace top by | Meaning |
|---|---|---|---|---|---|
Store one unmatched a | |||||
| Start matching and pop | |||||
Match another b | |||||
| or | Finish; leave the marker in place |
In particular, has no outgoing transitions. The transition from is available even if is nonempty; taking it early cannot accept because the input would remain unread. It does accept the empty word.
Proposition 9.1.2
(The block machine accepts exactly the equal blocks)
The machine of the table above, started in , accepts if and only if for some .
Proof
(Stack invariant, then both inclusions)
Before matching starts, after reading letters a, the stack is . Once a b is consumed, the machine is in and can never read another a. After reading along a run, the stack is ; that run exists only while .
For soundness, an accepting run either takes the final transition from with no letters read, yielding , or reaches after consuming some with . It can enter only with top , so . Because acceptance also requires the entire input to have been read, no later symbol is hidden from this reasoning. The accepted word is .
For completeness, given , push once for each a, pop once for each b, and take the final transition. For take it immediately. Thus every word in has an accepting run, and the two inclusions prove equality.
Proof X-ray
What each part of the machine is for
The proof rests on one invariant: in state the stack is after , and in it is after . Control and stack divide the work. The change happens on the first b and has no way back, so the control state enforces the order ; the stack enforces the count, because is on top exactly when . Since is never popped, "top is " is a reliable test that no a is unmatched, and the finishing transition is guarded by that test. It consumes no input, so acceptance also needs the input to be used up, which disposes of the early exit on a nonempty word.
Each part is necessary. If the finishing transition ignored the top symbol, aab would be accepted: the run reaches and could finish there. If were merged into , so that could both push and pop, then abab would be accepted: the stack goes .
Common mistake
(A final state is not acceptance)
Reaching is not enough; the input must also be used up. From the transition gives , a final state with the symbol b unread. Counting that as acceptance would accept b, which is not in . Only runs that end in with all input consumed count.
Worked example 9.1.3
(A complete run and three different failures)
For aabb, including the state changes and unread suffix:
aab finishes in with , so it has an unmatched a. In abb, the second b arrives when the top is , with no rule to consume it. In aba, the machine reaches after ab and has no rule to read the final a. The fact that one may take an early transition to does not rescue any of these inputs: that run leaves input unread.
Counterexample mode
Equal totals alone are not enough
Claim: every word with equally many a and b lies in . The word abab has two of each, yet it is not of the form . The machine rejects it: , and then a cannot be read in , while an early move to leaves ab unread. The stack checks the count, but the order is enforced by the change from to ; a count alone does not decide membership.
No delimiter: guess a split, then check it
Definition 9.1.4
(Reversal and even palindromes)
For a word , the reversal is written backwards. The language of even palindromes over is
Thus 0110 belongs to with ; 010 does not, because every word in has even length. The empty word belongs to .
Use pushing state , matching state and final state . Starting with stack , can read 0 or 1 and push the same symbol. At any point it may instead take an transition to without changing the stack. In , it may consume a 0 only when the top is 0, or a 1 only when the top is 1; the matching transition pops that symbol. Finally it may move from to by only when the top is , leaving in place. No transition returns to , no transition consumes , and has no outgoing transitions.
These rules make finitely many guesses on a fixed finite input: the phase switch can occur at most once, at one of the positions between symbols. There is no loop in this machine. The definition asks for an accepting finite run, not a magical ability to inspect the future.
Worked example 9.1.5
(A successful guess and an unsuccessful guess on the same word)
On 0110, push the first two symbols. The stack is , with 1 on top and unread input 10. Switch to , match and pop 1, then match and pop 0. With unread input empty and stack , enter : this run accepts.
If instead the machine switches immediately after the first 0, its top is 0 and the next unread symbol is 1. That run has no matching transition and fails. The word is nevertheless accepted because the split after two symbols gives a successful run.
Proposition 9.1.6
(The guessing machine accepts exactly the even palindromes)
The machine with states , , described above accepts a word if and only if the word belongs to .
Proof
(The stack holds the reversed prefix)
Suppose a run switches after reading a prefix . The pushing rules leave on the stack. In the matching phase, each consumed symbol must equal the current top and removes it. To reach , the machine must remove every symbol above ; to accept, it must also consume all input. Therefore the remaining input is exactly , and every accepted word has the form .
Conversely, for any , choose the phase switch immediately after . The stack is , and the second half matches and removes its symbols in order. Once only remains and the input is empty, the final transition accepts. The same argument covers . Hence the machine recognizes exactly .
Proof X-ray
Why one successful guess is enough
The proof is asymmetric, and that asymmetry is what nondeterminism means. For soundness it must cover every run, so it starts from an arbitrary switching point and shows that the word is . For completeness one run suffices, so it exhibits the single switch after . A word is accepted when some split works; the failing splits are irrelevant.
The invariant is that after pushing the stack, read from the top, is : a stack returns symbols in reverse order, which is exactly the order in which the second half must be read. The guard "top is " on the move to ensures that every pushed symbol was matched. Without it the run would accept 0, a word of odd length. The switch happens only once because no transition leads back to .
Worked example 9.1.7
(The smallest accepted words in both machines)
For the equal-block machine, the empty word uses only the finishing transition, , and ab runs . For the palindrome machine, the empty word needs two transitions, , and 00 with the split after one symbol runs . In every case the stack ends as with all input read. The empty word is the edge case: no symbol is ever pushed.
Counterexample mode
A failed run is not a rejection proof
On 0110, guessing the middle after the first symbol fails, but the guess after the second succeeds. To prove rejection, account for every possible split. For 010, a successful run would need to push and later pop the same number of input symbols, so the total length would be even. Its length is three; all splits fail. A single failed trace would not establish this conclusion.
Common mistake
(A stack reverses, so is not )
The machine recognizes , not . The word 0101 equals with , yet it is rejected. The only split with equal halves is after two symbols, where the stack is with top 1 while the next input symbol is 0; every other split fails by length or by a mismatch. The second half must be the reversal of the first.
If the input instead contains a single separator, the language has a visible phase boundary: push before #, switch when # is read, then match after it. For example 0#0 is accepted. The separator must occur exactly once, and acceptance still requires the entire suffix to be matched. This comparison explains the purpose of the guess; it does not by itself prove a general determinism or non-determinism theorem about other languages.
Check your understanding
Quick check
(Trace the equal-block machine on aabb. What is its stack immediately before and after the first b?)
Solution · Answer
Immediately before the first b, the state is and the stack is . Reading that b pops one and moves to , leaving . The second b leaves ; only then, with no input left, can the final transition accept.
Quick check
(Does the equal-block machine accept abba? Give a reason involving the unread input.)
Solution · Answer
No. After ab the machine is in with stack and unread input ba. It cannot consume the next b. It may enter by an transition, but ba remains unread and has no outgoing transitions. Thus no accepting run exists.
Quick check
(For input 1001, give a successful palindrome-machine split and the stack at that split.)
Solution · Answer
Choose . After pushing 1 and then 0, the stack is , with 0 on top. The remaining 01 matches and pops these symbols. The input is exhausted at , so the transition to accepts.
Quick check
(Can the palindrome machine accept 0011 by switching after 00? Does a different split help?)
Solution · Answer
After 00, the top is 0 and the next symbol is 1, so that split fails. Any accepting split must divide the four input symbols into two equal-length halves, because every pushed symbol must be popped by exactly one later symbol. Thus the only possible successful split is after two symbols; it fails, so 0011 is rejected.
The two examples use the same stack discipline for different reasons. Equal blocks use a visible change of input symbol to start matching; even palindromes use a nondeterministic split. In each case a proof specifies the invariant, proves every accepted word has the stated form, and gives a successful run for every word in the language.