Patterns and Machines

You use tonight's topic every day without calling it anything. You press Ctrl+F and type a word — that's a pattern. You type *.jpg to see just the photos in a folder — pattern. You put a name in a search box and the computer sorts a million pages into "matches" and "doesn't" — pattern again. Tonight we take that everyday habit seriously, and it turns out to be the same subject we've been studying for three weeks.

Here's the connection. So far, the way to describe a yes-pile has been to build a machine: draw the states, wire the arrows. A pattern is a second way — by typing. A pattern is a short piece of text that stands for a whole collection of strings: whatever fits it goes in the yes pile, everything else in the no pile. Same sorting job, new way of writing the job down.

And the week has one headline: the typed way and the drawn way describe exactly the same yes-piles. Every pattern can be turned into a machine, and every machine into a pattern; neither can do a job the other can't. We'll see both directions as pictures — machines snapping together like Lego — and you'll build the pattern-to-machine converter as the last milestone of Project 1.

A pattern is a recipe for writing yes-strings. If following the recipe could produce your string, it's a yes.

Plan: Tuesday, the three building blocks and lots of practice reading and writing them. Thursday, the two-way bridge to machines, and everything you get for free once it stands.

Everything in this section fits on an index card. A toy pattern is built from letters and exactly three ideas.

The surprise of the week is how far three blocks go. Let's build up to two piles you know well, on the alphabet {a, b}.

Warm-up: "ends with ab"

Start small. ab fits only the string ab. What fits any string of a's and b's, of any length? Offer the choice, then repeat it: (a|b)* — "an a or a b, over and over, as many as you like, even none." Now glue the two together:

(a|b)*ab

Read left to right: "anything at all, then an a, then a b." That's exactly the pile of strings ending in ab — last week's guessing-machine job, in eight keystrokes.

Harder: "an even number of a's"

This one takes honest fumbling, so let's fumble honestly. Attempt one: (aa)* — "the block aa, repeated." Every string it writes has its a's in pairs, good — but it can never write a b. The string abba belongs in the pile and this recipe can't produce it. Too strict.

Attempt two: (a|b)* — "anything." Now abba fits, but so does a, which has one a. Way too loose.

The fix comes from saying the job out loud: the a's come in pairs, with b's free to sit anywhere around them. So — let some b's go by, then repeat this unit: an a, some b's, a second a, some b's:

b*(ab*ab*)*

Every a this recipe writes arrives locked in a pair. Two a's, four a's, zero a's — all reachable; three a's — impossible, however you follow it. Compare with the two-state machine from Notes 02 doing the same job: same pile, wildly different-looking descriptions. Hold that thought for §04.

A pattern is only useful if you can say what it means without hesitating — that skill is half the week. Two gotchas cause nearly every misreading.

Gotcha one: the star grabs almost nothing. It repeats only the one thing right before it. So ab* is "an a, then any number of b's" — a, ab, abbb. It is not "ab repeated." Want the whole block repeated? Say so with parentheses: (ab)* — the empty string, ab, abab, and so on.

Gotcha two: the or-bar grabs everything. It takes as much as it can on both sides, stopping only at a parenthesis. So ab|ba is "ab, or ba" — the bar took the whole ab and the whole ba. And a|b* is "one a, or else any number of b's" — the star grabbed its b first (stars act before bars), then the bar took all that was left. To make a small choice inside a bigger pattern, fence it in: a(a|b)a — "an a, one letter of either kind, an a."

A reading table. Cover the right column and translate each pattern yourself first — out loud, ideally.

The last two are old friends: "contains bb" was a Notes 02 machine, and "exactly one a" would make a fine three-state design exercise.

Now drive it yourself. The tester below speaks only the toy language — letters, the or-bar, parentheses, the star — and it doesn't cheat: behind the scenes it builds your pattern into a guessing machine (the §04 construction) and runs the copies tracker from Notes 03 on your string. The log is the same "chips lit" story you already know.

Worth trying: give a* the empty string (yes — zero repeats is allowed). Give (ab)* the string ab, then aba. Feed the even-a's pattern strings until you trust it. Then break things on purpose — a stray star, an unclosed parenthesis — and read the complaints.

Now the big claim, one direction at a time. Direction one: any pattern can be turned into a guessing machine that sorts the same pile. The construction is pure Lego. The smallest brick is the machine for a single letter — a start chip, one arrow that reads the letter, a finish chip; that's the entire machine for the pattern a. The three combining ideas are three ways of snapping bricks together, and the free moves from Notes 03 — arrows followed without reading a letter — are the snaps. Watch where they go; the bricks themselves never get rewired.

Snap 1 · "then" — chain them

Snap 2 · "or" — side by side, sharing a start

Snap 3 · "repeat" — a loop back, and a skip

That's the entire construction. Build any pattern inside-out — smallest bricks first, snapping as you go — and out comes a guessing machine, exactly the species you tamed last week. It says yes to precisely the strings the pattern fits, because every choice the recipe offers (which side of the or, how many laps of the star) becomes a fork the machine can guess through. And since Notes 03 turns any guesser honest, every pattern ends up as an honest machine. Typed description in, runnable machine out.

Watch it happen. Pick a pattern and step through the build. Dashed amber arrows are free moves; the highlighted piece is the brick being added right now.

Notice how wasteful the result looks — chips whose only job is to pass a copy along by free move. That's fine. The construction optimizes for obviousness: you can point at any chip and name the piece of the pattern that put it there. Thrift is the honest machine's department, one conversion later.

Direction two runs the other way: hand me any machine — honest or guessing — and I can write a pattern for its yes-pile. The idea fits in one paragraph, because it's a picture.

Squeeze out the machine's states, one at a time. A squeezed state can't just vanish — trips used to pass through it. So before it goes, write what a trip through it contributed — "an a, then any number of b's, then an a," say — onto a new arrow that bypasses it. The arrows' labels fatten from single letters into little patterns, but the machine keeps sorting the same pile. Keep squeezing. When only a start and a finish remain, the label on the one arrow left is a pattern for the whole machine.

We won't drill this direction — no recipe to memorize, no homework on it. It's enough to see the picture and believe it: nothing about a machine is un-typeable. Between §04 and this, the two-way bridge stands:

Patterns and machines are two languages for the same thing. Anything you can type, a machine can run; anything a machine can sort, you can type.

One naming note, since Project 1 and every book use it: these typed patterns are called regular expressions, and the yes-piles that patterns-and-machines can describe are the regular languages. "Regular" is just the family name. Next week is about the piles outside the family — they exist, the counting language is one, and we'll learn to prove it.

The bridge pays for itself immediately. Suppose you own a machine for job A and a machine for job B — say A is "even number of a's" and B is "ends with ab." What other jobs do you get for free, with no new design work?

• "A or B." Snap 2: one new start chip, free moves fanning into both machines. Done.
• "A then B" — strings that cut into a front half A likes and a back half B likes. Snap 1: chain with a free move.
• "Repeat A" — strings that slice into pieces A likes. Snap 3: loop and skip.
• "Everything EXCEPT A." A different trick, and a lovely one: take the honest machine for A and swap the yes-states — every yes becomes a no and every no a yes. Same walk for every string, opposite verdict. Two lines of Python.
• "Both A and B at once." Put one finger on A's start state and one on B's. Each letter moves both fingers, each by its own rule table. A "state" of the combined machine is just the pair of places your fingers are — finitely many pairs, so it's a perfectly legal honest machine. Say yes when both fingers rest on yes-states.

One warning about the swap trick: it only works on the honest machine. On a guessing machine it lies. Concretely: last week's "ends with ab" guesser says yes to ab because one bold path wins — but a timid path also exists, ending in the skimming state, a no-state. Swap the yes-states and the timid path's home becomes a yes-state — so the swapped machine also says yes to ab. Yes to "ends with ab" and yes to "doesn't end with ab," on the same string. The guesser's own rule is the problem: yes needs only one winning path, so flipping the goalposts doesn't flip the answer. Make the machine honest first — one walk, one verdict, safe to flip.

The family of machine-doable jobs is closed. Combine them however you like — or, then, repeat, except, both — and you land back inside the family.

Hold this section like a box of Lego: snapping Lego together only ever produces Lego. You cannot escape the family by combining its members — no pile-up of ors and thens and excepts will ever build the counting language. Which raises the obvious question: how do you ever show a job is outside the family? Not by building — you need a tool for proving a negative, a wall in Notes 01's flavor-2 sense. That tool is next week.

Project 1's last milestone is exactly tonight's §04: compile a pattern into a machine. Your finished simulator becomes a pipeline — the same one every real search tool runs:

pattern  →  guessing machine (tonight's Lego)  →  honest machine (last week's conversion)  →  run_dfa (Week 2's ten lines)

The compile step is small because the snaps are the code. Read the pattern into a little tree — letters at the leaves, then / or / repeat at the branches — and walk it, building bricks:

def build(node):
    # Returns the piece's start chip and finish chip.
    # Free moves are arrows labeled "" — they read nothing.
    if node["kind"] == "letter":            # the smallest brick
        s, e = new_chip(), new_chip()
        arrow(s, node["ch"], e)
    elif node["kind"] == "then":            # snap 1: chain
        s, e = build(node["first"])
        s2, e2 = build(node["second"])
        arrow(e, "", s2)                    # the free-move handoff
        e = e2
    elif node["kind"] == "or":              # snap 2: fan out
        s, e = new_chip(), new_chip()
        for part in node["parts"]:
            ps, pe = build(part)
            arrow(s, "", ps); arrow(pe, "", e)
    else:                                   # snap 3: loop and skip
        ps, pe = build(node["inside"])
        s, e = new_chip(), new_chip()
        arrow(s, "", ps); arrow(pe, "", e)  # in and out
        arrow(pe, "", ps)                   # around again
        arrow(s, "", e)                     # or skip — zero repeats
    return s, e

Test it the way you tested the conversion: agreement. For every short string you can generate, the compiled machine's verdict must match a direct check of the pattern. The §03 tester on this page runs this exact construction — when your Python disagrees with it, one of us has a bug, and finding out which is a genuinely good evening.

Six questions. Decide on your answer before you click — being wrong here is free, and useful.

Project 1 is in full swing — due at the end of next week — and tonight handed you its final milestone. Next week we find the edge of the regular family, so arrive with the pattern–machine bridge feeling solid.

Coming up

Sessions 8 and 9 (Sept 29, Oct 1) — Notes 05. The wall, at last: a way to prove a job is outside the regular family — no pattern, no machine, no cleverness — plus a way to find the smallest honest machine for any job inside it. Project 1 is due that week.

If anything tonight didn't land, email me — yair.chaya@liu.edu — or grab an office-hours slot. I reply within 24 hours.