Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 59 · Pushdown Automata

PDAs for Matching Counts: a^n b^n and Friends

Design pushdown automata for languages where one block of symbols must match another: a^n b^n c^m, a^n b^m c^n, a^m b^2m and more, with Python checks.

Many exam questions on pushdown automata are variations of one idea: count one block of symbols with the stack, then compare it with another block. Once you see the pattern, a dozen languages with different exponents collapse into a few templates. This lesson works through the matching templates; the next lessons cover sums of counts and either/or conditions.

All machines accept by final state, use $ as the bottom marker, and are tested against a plain Python predicate on every string up to a length bound. If you have not seen the simulator yet, read the introduction first.

The three templates

  1. Push, then pop, then ignore: a^n b^n c^m. The tail does not care about the stack.
  2. Push, skip, pop: a^n b^m c^n. The middle block leaves the stack unchanged.
  3. Push several symbols per input symbol: a^m b^{2m}, a^{2m} b^{3m}. Multiples are handled by pushing more (or by counting parity in the state).
flowchart LR
    A["Phase 1<br/>read a's, push"] --> B["Phase 2<br/>read b's, pop or skip"] --> C["Phase 3<br/>read c's, pop or ignore"] --> D["Accept when only $ is left"]

Every design in this lesson is a chain of phases like this.

Template 1 and 2: a^n b^n c^m and a^n b^m c^n

For a^n b^n c^m (with n, m ≥ 1): push on a, pop on b, then when the stack shows $ allow any number of cs. For a^n b^m c^n (n, m ≥ 1): push on a, then read the bs without touching the stack (rewrite the top symbol as itself), then pop on c.

Python Two machines: a^n b^n c^m and a^n b^m c^n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both lists are empty, so the machines agree with the predicates on all 3^0 + … + 3^9 strings. Note the trick in L2: the transition ("q1", "b", "A", "q1", "A") reads a b, pops A and pushes A back, so the stack is unchanged while the state records that we are in the b phase. The transition ("q0", "b", "A", "q1", "A") requires at least one b.

Template 3: multiples with push counts

For a^m b^{2m} with m ≥ 1 the stack must hold twice as many markers as there are as. Push two As per a: the rule a, $ / AA$ and a, A / AAA. Each b then pops one. For a^m b^{2m+1} do the same, then allow one extra b when only $ remains.

For a^{2m} b^{3m} the pair of as is worth three markers. Use two states q0 (even number of as so far) and q1 (odd), pushing three markers on the first a of each pair and nothing on the second.

Python a^m b^2m, a^m b^(2m+1) and a^2m b^3m

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the first machine on aabbbb by hand: after aa the stack is AAAA$; four bs pop four markers; the ε-move ε, $ / $ fires and we accept. For aabbb three markers are popped and one A remains, so the ε-move cannot fire (its top must be $) and the string is rejected.

Two languages with a choice: a^n b^n ∪ a^n b^{2n}

A union of two matching languages needs nondeterminism: after the first a, the machine guesses which branch it is in. Branch 1 pushes one A per a; branch 2 pushes two. Each branch has its own pop phase.

flowchart LR
    S(["q0"]) -->|"a, $ / A$"| P1(("p1"))
    S -->|"a, $ / AA$"| P2(("p2"))
    P1 -->|"a, A / AA"| P1
    P2 -->|"a, A / AAA"| P2
    P1 -->|"b, A / ε"| Q1(("r1"))
    Q1 -->|"b, A / ε"| Q1
    P2 -->|"b, A / ε"| Q2(("r2"))
    Q2 -->|"b, A / ε"| Q2
    Q1 -->|"ε, $ / $"| F((("qf")))
    Q2 -->|"ε, $ / $"| F
Python The union a^n b^n ∪ a^n b^2n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a language is a union of two simpler ones, build each machine separately and join them with a nondeterministic first move. This is the PDA version of the NFA union construction.

Common mistakes

  • Forgetting the lower bound. n ≥ 1 and n ≥ 0 are different languages. With n ≥ 0 you must also accept the empty string, and "skip the first block" needs an ε-move.
  • Accepting too early. The accepting move should demand $ on top. Without that test, strings with leftover markers sneak in.
  • Popping from the wrong symbol. In a multi-symbol stack alphabet, be explicit about which symbol each phase pops.
  • Not testing near misses. Always check aab, abb, ba and abab-style strings, not only the good ones. The agrees helper does this exhaustively.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In a PDA for a^n b^m c^n (n, m >= 1), what should the machine do to the stack while reading the b's?

    The b's are unrelated to the count of a's, so the markers must stay until the c's can match them.
  2. 2. How do you build a PDA for a^m b^(2m)?

    Two b's are needed for each a, so each a is worth two markers and each b pays back one.
  3. 3. Why must the language a^n b^n ∪ a^n b^2n be handled with nondeterminism?

    The right branch is revealed only when the b's end; a nondeterministic machine tries both in parallel.
  4. 4. What makes the final ε-move ε, $ / $ important?

    Because the move requires $ on top, leftover markers block it and the string is rejected.

Summary

  • Matching languages follow the pattern push block 1, skip or pop block 2, pop block 3.
  • To skip a block without changing the stack, replace the top by itself (b, A / A).
  • Multiples are encoded by pushing several markers per symbol, or by tracking parity in the state.
  • Unions of matching languages need a nondeterministic first move.
  • Verify every design exhaustively against a Python predicate for short strings.

Next: PDAs for sums of counts