Machines With a Stack

Two weeks ago, the pumping lemma showed that "some a's followed by the same number of b's" has no finite machine. Last week, a two-rule grammar built that language with no effort at all. So we have a description but no machine. This week we build the machine, and it turns out to need only one new part.

Think about what goes wrong for a DFA. To check aaabbb, it has to remember "I've seen three a's" while it reads the b's. To check a hundred a's, it has to remember a hundred. A DFA's only memory is which state it's in, and it has a fixed number of states. Sooner or later the string is longer than the machine can count.

Here's how a person would do it. Picture a bouncer at a club door with a clicker: click up for every person who walks in, click down for every person who walks out, and the club is empty when the clicker reads zero. That works for one kind of thing. Now make it harder: parentheses and square brackets, like ( [ ] ( ) ). A count isn't enough any more. When a closer arrives, you need to know which kind of opener was the most recent one. You need to remember the order things were opened in, and you only ever need the most recent one.

There is a very old, very simple kind of memory that does exactly that. It's called a stack.

A finite automaton can count only as high as its number of states. Give it a stack, and it can follow nesting as deep as the input goes.

Think of the spring-loaded plate dispenser in a cafeteria. You can put a clean plate on top. You can take the top plate off. You can look at the top plate. That's all. You can't pull a plate out of the middle, and you can't see what's underneath without taking plates off first. The last plate you put on is the first one you take off.

You use stacks every day. The browser's back button is one: each page you visit is pushed, and Back pops you to the most recent one. Undo in a text editor is another: each edit is pushed, and Undo pops the latest. When Python calls a function from inside a function, it pushes where it was, and pops back there when the inner call returns. That's literally called the call stack, and it's what you see in an error traceback.

Now watch a stack check brackets. Read left to right. Push every opener. At every closer, pop the top and check that it's the matching kind. Here's ( [ ] ( ) ), with the stack written top first:

The string is balanced: every closer matched the top, and the stack is empty at the end.

Two things can go wrong. A closer can arrive and find the wrong kind on top, as in ( [ ) ], where the ) finds a [. Or the input can end with something still on the stack, as in ( (, where an opener never got closed. Those are the only two ways to fail, and the stack catches both.

A pushdown automaton (PDA) is the finite automaton you already know, with a stack bolted on. It still has states and arrows, a start state, and accepting states. The difference is in what one move does. A DFA's move only reads a symbol and changes state. A PDA's move can also look at the top of the stack and change it.

Some books use a different rule: accept when the stack is empty, whatever the state. The two rules turn out to be equally powerful, so we'll stick with accepting states, since that's what you're used to from DFAs.

The machine for "some a's, then the same number of b's"

The plan is the plate dispenser. Push one plate for each a. Take one plate off for each b. If the plates run out exactly when the input does, the counts matched. One extra trick: before reading anything, put a special plate, $, at the very bottom. A PDA can only see the top, so it has no direct way to ask "is the stack empty?" Instead, it asks "is $ on top?" That's the bottom marker, and almost every PDA you write will use one.

In words: state s lays down the bottom marker. State p reads a's and pushes one A for each. The first b moves to state r, and from then on every b takes one A off. When $ shows up on top, every A has been matched, and a free move pops $ and goes to f. The move from p straight to f is for the empty string, zero a's and zero b's, which is in the language too.

Here is the run on aabb, one move per line:

All input read, and the machine is in f. Accept.

Now see it fail. On aab, the input runs out in state r with A still on top. The only way to f is to pop $, and $ is buried under an A, so the machine is stuck in a non-accepting state. Reject. On abb, the second b arrives with $ on top and no A to pop. Stuck again, with input left over. Reject. On aba, the last a arrives in state r, and r has no move for a at all. Reject.

Try it in the lab. Pick a machine, type a string, and press Step to make one move at a time. The tape shows where the machine is reading, the table lights up the move it just used, and the stack on the right grows and shrinks. Then try strings that should fail, and read why they fail.

Good strings to try with the first machine: aaabbb, ab, the empty string, then aab, abb, abab, and ba. With "twice as many b's", try aabbbb and aabbb. The only change in that machine is that each a pushes two A's, so each a has to be paid back with two b's. (It's the grammar S → aSbb | ε from last week's Think first, as a machine.)

The a's-then-b's machine pushes the same symbol every time, so its stack is really just a counter. The bouncer's clicker would do the same job. The bracket machine is where the stack earns its name. Switch the stepper to balanced ( ) and [ ]. It has one working state, q, and the rule from §02:

• Read ( : push ( . Read [ : push [ . (Push the opener itself, so the stack remembers which kind it was.)
• Read ) : pop ( . Read ] : pop [ . (A closer can only be read if its own kind is on top.)
• Read nothing, pop $ : go to f. (Everything opened has been closed.)

Run it on ([]()) and watch the stack: it holds the list of brackets that are open right now, most recent on top. Then run ([)]. The ) arrives with [ on top, no move fits, and the machine stops right there. The stepper tells you exactly which symbol it choked on. That's the same kind of error message a code editor gives you for a mismatched brace, and it's computed the same way.

This is also why every serious language tool, from the Python interpreter to your browser's HTML reader, keeps a stack while it reads. Nested folders inside folders, function calls inside function calls, tags inside tags: anything that opens and closes in nested order is a stack's job.

Here's a language that looks just as friendly: even-length palindromes over a and b, such as abba, baab, aa, and the empty string. Each one is some string followed by the same string backwards. The stack plan writes itself: push the first half, letter by letter, then pop the second half, checking that each letter matches the top. The stack reverses the first half for free, because the last letter pushed is the first one popped.

There's one problem. Reading left to right, how does the machine know when it has reached the middle? It can't. After reading ab, the string might be abba (middle reached), or abbbba (middle after abb), or abaaba (middle after aba). Nothing on the input marks the middle.

So the machine guesses, the same way the NFAs of Notes 03 guessed. In state p it pushes each letter it reads. At any moment it may take a free move to state m, which means "I bet this is the middle." In state m it reads a letter and pops it, and only if the top matches. When $ shows up on top, a free move goes to f.

Remember the two readings of guessing from Notes 03: the lucky guesser, and parallel worlds. The parallel-worlds reading works here too, with one change. Each world now carries its own stack. When a world splits, both copies get their own copy of the stack and go their separate ways. A world dies when it has no move that fits. The string is accepted if, when the input ends, at least one world is in f.

The tracker below runs that reading. Each card is one living world: its state on top, its stack underneath. Worlds that die on a step are shown faded, with the reason. Start with abba and press Step slowly. You'll see a new "this is the middle" world split off at every position. Every guess dies except the one made right after ab. The world that never guesses survives to the end too, but it is still in p, pushing, so it doesn't count.

Try abba, then abab (every guess of the middle dies; only the world that never guessed is left, still pushing, and it never reaches f), then aba (odd length: no middle between two letters works), then the empty string (the guess "the middle is right here, before anything" wins at once). The other three machines in the menu come from §06; ignore them for now.

This time, the guessing can't be compiled away

In Notes 03, guessing turned out to be a convenience. The set of living worlds was always a set of states, there are only finitely many of those, and so a plain DFA could track the whole set. Every NFA had a DFA twin. The aside at the end of that week promised that stack machines would be different, and here's where that pays off.

Look at the tracker on a longer palindrome. Each world carries its own stack, and the stacks are all different. A machine with no guessing has one stack. It can't keep all those stacks at once in a single one. And for even palindromes, no clever design gets around this: there is no deterministic PDA for even-length palindromes. Machines that never have a choice to make are strictly weaker than machines that can guess. We won't prove it, but the tracker shows you why it's believable.

Why should you care? Because a real parser can't afford to guess. A guessing machine, run on a computer, means trying many worlds or backtracking when a guess goes wrong, and that gets slow. So programming languages are deliberately designed so that a parser can always tell what to do next by looking at the next token or two. A while keyword means a loop is starting. A ( means a group is opening. Nobody has to guess where the middle is. Next week's "parsing in practice" is about exactly this.

Notes 06 ended with a promise: grammars and stack machines define the same languages. Here's the half of that promise you can actually use. Any grammar can be turned into a PDA, with a recipe so simple it almost feels like cheating.

The idea: use the stack to hold the part of the string the machine still expects to see. Start by putting the start variable on the stack. Then repeat:

• If the top is a variable, guess one of its rules and replace the variable with that rule's right side. (Pop the variable, push the right side, with its first symbol on top.) This reads nothing.
• If the top is a terminal, it's a prediction about the next input symbol. Read the next symbol. If it matches, pop it. If not, this world dies.
• If the top is $, every prediction came true. Pop it and accept, if the input is used up.

That's the whole machine. It has just three states (start, loop, and f). Almost all the work happens in the loop state, and all the knowledge of the language sits in the rules.

Here it is on the grammar S → aSb | ε and the input aabb. The stack is written top first, and the world shown is the one that guesses right each time:

Input used up, machine in f: accept.

Look at any row and glue the input read so far to the stack (without the $). In the fourth row, the input read is a and the stack is aSbb, which glue together into aaSbb. That's exactly a step of the leftmost derivation from Notes 06: S ⇒ aSb ⇒ aaSbb ⇒ aabb. The PDA is running the derivation, one rule at a time, and checking each terminal against the input as soon as it appears on the left. That's why the guess is about the top variable: it's the leftmost one.

Go back to the tracker in §05 and choose one of the grammar machines. Try S → aSb | ε on aabb, S → (S)S | ε on (())(), and the palindrome grammar on abba and aba. Variables on the stacks are shaded. Watch how a variable on top always splits a world into one copy per rule, and how the copies whose top terminal doesn't match the next input die right away. Wrong guesses never live long.

And back again

The other direction is true too: any PDA can be turned into a grammar. That construction is longer and fiddlier, with one variable for each pair of states, and we'll leave it to the textbook. What matters is the result. Grammars and PDAs are two doors into the same room. The languages they describe are called the context-free languages, just as patterns and finite automata were two doors into the room of regular languages.

The first three rows are the regular room. The last three connect it to the context-free room above it: every DFA is a grammar, every grammar is a PDA, and every PDA is a grammar again.

As before, each door is good at a different job. A grammar is the best way to write down a language: it's short, it reads like a definition, and it gives you parse trees. A PDA is the best way to check strings: it reads left to right with a stack, which is what a parser actually does.

A PDA fits in a dictionary, just like the DFAs of Project 1. Each move is a tuple of five things: the state it starts from, what it reads, what it pops, what it pushes, and the state it goes to. An empty string means "nothing." To keep things short, every symbol is one character and the stack is a string with its top at the right-hand end. The push part is written top first, the same way as the tables above.

A_N_B_N = {                         # some a's, then the same number of b's
    "start": "s",
    "accept": {"f"},
    "moves": [
        # from  read  pop  push  to
        ("s", "",  "",  "$", "p"),      # lay down the bottom marker
        ("p", "a", "",  "A", "p"),      # one A for each a
        ("p", "b", "A", "",  "r"),      # first b: start taking A's off
        ("r", "b", "A", "",  "r"),      # one A off for each b
        ("p", "",  "$", "",  "f"),      # marker on top: all matched
        ("r", "",  "$", "",  "f"),
    ],
}

EVEN_PAL = {                        # even-length palindromes over a, b
    "start": "s",
    "accept": {"f"},
    "moves": [
        ("s", "",  "",  "$", "p"),
        ("p", "a", "",  "a", "p"),      # first half: push each letter
        ("p", "b", "",  "b", "p"),
        ("p", "",  "",  "",  "m"),      # guess: this is the middle
        ("m", "a", "a", "",  "m"),      # second half: letter must match the top
        ("m", "b", "b", "",  "m"),
        ("m", "",  "$", "",  "f"),
    ],
}

To run a machine that guesses, we do what the tracker does: follow every world. A world is everything the machine needs to carry on: its state, how much input it has read, and its stack. Put the first world in a queue. Take worlds out one at a time, and for each move that fits, add the world it leads to. If any world has read the whole input and is in an accepting state, accept. If the queue runs dry, every world died, so reject. That's a breadth-first search, the same one the NFA simulator in Project 1 used, with stacks added.

from collections import deque

def accepts(pda, w, max_stack=50):
    """Try every world (state, position, stack), breadth-first."""
    start = (pda["start"], 0, "")
    queue, seen = deque([start]), {start}
    while queue:
        state, pos, stack = queue.popleft()
        if pos == len(w) and state in pda["accept"]:
            return True                          # some world made it
        for frm, read, pop, push, to in pda["moves"]:
            if frm != state:
                continue
            if read and (pos == len(w) or w[pos] != read):
                continue                         # wrong input symbol
            if pop and not stack.endswith(pop):
                continue                         # wrong top of stack
            new_stack = stack[:len(stack) - len(pop)] + push[::-1]
            if len(new_stack) > max_stack:
                continue                         # guard against endless pushing
            world = (to, pos + len(read), new_stack)
            if world not in seen:
                seen.add(world)
                queue.append(world)
    return False                                 # every world died

print(accepts(A_N_B_N, "aabb"))    # True
print(accepts(A_N_B_N, "aab"))     # False: an A is left on the stack
print(accepts(EVEN_PAL, "abba"))   # True
print(accepts(EVEN_PAL, "aba"))    # False: odd length

Two details deserve a second look. First, push[::-1] reverses the push string before adding it, so that the symbol written first ends up on top. Second, the two guards. The seen set skips worlds we've already tried. The max_stack limit stops a machine with free moves that push forever, like a grammar with a rule E → E + T, whose machine can keep replacing E with E + T without reading anything. Without that limit, the search would never end. With both guards, there are only so many different worlds, so the search always finishes. Raise max_stack if your inputs are long.

The recipe from §06 is just as short. It turns a grammar, written as a dictionary the same way as in Notes 06, into a PDA that the same accepts function can run:

def grammar_to_pda(grammar, start):
    """Expand-and-match PDA for a grammar with one-character symbols."""
    moves = [("s", "", "", start + "$", "L")]    # start variable on top of $
    terminals = set()
    for var, rules in grammar.items():
        for rule in rules:
            moves.append(("L", "", var, "".join(rule), "L"))   # top is a variable: guess a rule
            terminals.update(s for s in rule if s not in grammar)
    for t in sorted(terminals):
        moves.append(("L", t, t, "", "L"))       # top is a terminal: match the input
    moves.append(("L", "", "$", "", "f"))        # marker on top: every prediction came true
    return {"start": "s", "accept": {"f"}, "moves": moves}

PARENS = {"S": [["(", "S", ")", "S"], []]}       # S -> (S)S | ε, from Notes 06

parens_pda = grammar_to_pda(PARENS, "S")
print(accepts(parens_pda, "(()())"))   # True
print(accepts(parens_pda, "(()"))      # False

Notice that the grammar's ε rule becomes the move ("L", "", "S", "", "L"): pop S, push nothing. The placeholder just disappears, exactly as it does in a derivation.

Six questions. Answer before you click. Being wrong here costs nothing and teaches you something.

This week gave grammars their machine. Between the grammar from last week and the PDA from this week, you have both halves of Project 2 — Invent a Tiny Language, due Monday, November 9, 11:59 PM — so this is a good week to get your grammar through the certifier.

Coming up

Sessions 14 and 15 (Oct 20, 22): Notes 08. First, the pumping lemma for context-free languages. It's the grammar version of the tool from Notes 05, and it shows that "equal a's, b's, and c's, in that order" has no grammar and no PDA, the teaser from Notes 06. Then, parsing in practice: how real parsers avoid guessing by looking one token ahead.

If any part of this week didn't land, email me at yair.chaya@liu.edu or ask for an office-hours slot. I reply within 24 hours.