Where Patterns End

For four weeks, every job we touched turned out to be doable: design the states, or type the pattern, done. Last week ended on a promise — tonight we find the edge. You'll meet a job that looks like a warm-up and is actually impossible, and you'll learn to prove impossibility yourself. Not "I couldn't find a machine." Nobody ever will.

The job: some a's, then exactly that many b's. The yes pile is ab, aabb, aaabbb, and on up — the counting language that has haunted these notes since Week 1. Or, dressed for work: matching brackets — every open bracket closed, every close bracket earned. Same job in programmer's clothes, and every compiler on Earth has to do it.

Try to build the machine. Honestly try — this failure is the whole lesson. The design question from Notes 02: while the a's stream past, what's the least you must remember? The count. Not a digest of the count, the count itself, because at the end every single a must be answered by a b. So you lay out states: "no a's yet," "one a," "two a's," "three a's"…

Feel the failure? Every attempt ends the same way: counting with no ceiling, using a memory with a fixed size. However clever the design, some two different counts end up sharing a state — and Notes 02 told us what that means: the difference between them is forgotten for good. Tonight we sharpen that feeling into an actual proof.

"I tried hard and failed" convinces nobody. Tonight's trick convinces everybody — including the machine's biggest fan.

Plan: Tuesday, the loop trick and the game you play with it. Thursday, the other side of the coin — counting memories and shrinking machines — plus Project 1, due this week.

One observation powers the entire evening. A machine has a fixed handful of states — say ten. Walk a long string through it: every letter is a step, so fifteen letters make a walk of sixteen visits (count the one before the first letter). Sixteen visits, ten states — sixteen guests, ten chairs: somebody sits in the same chair twice.

The piece of the walk between the two visits — leave a state, wander, come back — is a loop. Every long enough walk has one. Always.

Now the sneaky part. Going around the loop reads some chunk of letters and lands you right back where you started — so nothing stops another lap. Or ten. Or walking straight past without entering. The machine can't object: it has no lap counter, no memory beyond "which state am I in." Which gives us:

Let's swing it at the counting job. A skeptic claims a machine — we ask one question: how many states? Say ten. Feed it ten a's, then ten b's. In the pile, so the machine says yes. But the walk's first eleven visits happen while reading the first ten letters — all a's — so the loop sits entirely inside the a's; its chunk is pure a's, at least one. Pump it twice: the a's grow, the b's don't. Out of the pile — and the machine still says yes. Caught. A hundred-state machine? Same trap, a hundred a's. Bigger machine, longer bait, same ending.

A machine is a creature of habit: whatever it does in a loop, it will happily do forever. Jobs that can't tolerate that are jobs no machine can hold.

A bit of trivia: textbooks call this the pumping lemma. Around here it stays the loop trick — walk long enough, revisit a chair, rerun the round trip.

Now get your hands on it. Below: one correct machine, and two seductive attempts at the counting job that count on a clock face and quietly wrap around. Feed each a long yes-string, watch the forced loop light up, then pump — and watch what breaks, and what doesn't.

Worth trying: pump the correct machine and notice nothing ever breaks — that's what "pattern-shaped" feels like. Pump a clock attempt ×0 and watch a's vanish while every b stays. And feed an attempt a short string: no loop, no trick — which is why small test cases never catch this kind of bug.

Writing a loop-trick argument can feel slippery — where's the loop? how long is the string? Here's the fix: the whole thing is a two-player game with fixed turns; play your turn well and you cannot lose. Every impossibility proof in this course is you winning this game in writing.

Step 3 is where everyone slips, so hear it twice: you must beat every loop, not just a convenient one. The loop lands wherever the walk puts it; your only power is the string — so choose one where every legal loop location is poison.

A full round: strings that read the same backwards

Let's play a complete game against palindromes — strings that read the same backwards, an old friend from Notes 01's tester. The skeptic opens: "my palindrome machine has forty states."

Your move: forty-one a's, one b, forty-one a's. Backwards it's the same — in the pile. And here's the craftsmanship: the first forty-two visits happen while reading the first forty-one letters, and forty-two visits into forty states forces the revisit early — the loop's chunk lives entirely inside the front run of a's. Wherever exactly it falls, it is some a's.

Now pump twice. The front run of a's grows; the b doesn't move; the back run is still exactly forty-one. Front and back no longer match — not a palindrome, out of the pile — and the machine still says yes, because loops can't be counted. The skeptic mutters "fine, eighty states." You answer "eighty-one a's, a b, eighty-one a's." There is no number they can name. No machine sorts palindromes. Ever. (Notice: flavor 2 from Notes 01 — assume it works, walk into the wall — with the loop trick supplying the wall.)

Thursday's idea comes at the wall from the other side. The loop trick catches machines misbehaving; this one asks, before any machine exists: how many different things does the job force a machine to remember? Answer that and you know everything — whether a machine exists, and how big the smallest one is.

Here's the test. Take two possible beginnings of input — say the machine has read a so far, versus aa — and ask: does some ending finish one of them in the yes pile but not the other? If yes, the two must never share a state: sharing is forgetting, and that ending would then get a wrong verdict. If no ending ever tells them apart, they can happily share. So picture sorting all possible beginnings into memory drawers: same drawer only when no ending distinguishes.

Why must a, aa, aaa all get different drawers in the counting job? Take a and aaa: the ending "one b" finishes the first into the pile (ab) and leaves the second out (aaab). Different drawers. The same move separates every pair of a-runs — the ending with exactly as many b's as one of them says yes to it and no to the other. One drawer per count. Endlessly many.

Sit with how strong that is: not a trick that catches machines, but a census that settles the question before anyone builds anything — and it hands you a number, not just a verdict. "Even number of a's" forces exactly two drawers, so Notes 02's two-state machine wasn't just correct, it was the smallest possible — provable now. (Textbooks call this drawer census the Myhill–Nerode theorem; you've just done the entire idea with furniture.)

The drawer census says a smallest machine exists. Here's the practical question: your machine works, but is it carrying dead weight — and how would you shed it? The answer is a merging game, and it runs on one word: twins.

Two states are twins if every possible future treats them identically: start from either, feed in any ending, and the verdicts always agree. Twins are two labels on the same memory drawer — merging them changes nothing the outside world can see. So:

Watch it on a real case: a five-state machine for "contains bb somewhere" — Notes 02 did it with three, and this bloated cousin carries two freeloaders. The tinted pairs are the twins: A and D both mean "no bb yet, last letter wasn't b"; C and E both mean "bb found, yes forever." Merge both pairs and the honest three-state machine reappears.

Do it yourself below. Click two states and test them: twins get merged, and non-twins earn you the exact ending that catches the difference. Watch the plain-words meanings as you go — the twins had the same meaning all along. Bloat is two names for one memory; minimizing is noticing.

Why Project 1 graders love this: two students hand in different-looking machines for the same language — different names, different shapes, six states versus nine. Shrink both. If the slim machines match (up to renaming), the students agree; if not, some ending separates them — a failing test case, gift-wrapped. Uniqueness turns "do these machines agree?" into a mechanical check.

Tonight's two ideas snap together into a field procedure you'll use for the rest of the course — and the rest of your career, whenever someone says "just write a regex for it."

1. Ask the memory question. What must be remembered about the input so far? Try to list the drawers.
2. Drawers form a short list? The job is pattern-shaped. Build the machine — one state per drawer — and you know the smallest size in advance.
3. Drawers keep coming forever? The job is outside the family. To convince someone else, win a round of the skeptic game in writing: their number, your string, every loop poisoned.

The census in table form. Count the drawers and the whole question — possible or not, and how big — answers itself.

One closing thought. The wall is real, but it's a wall for this machine, not for computing — "matching brackets" is impossible tonight and routine for every compiler, because compilers bring more memory to the fight. Next week we meet the first tool that does: grammars, a new kind of describing power that builds strings from the inside out, and the counting language falls to it on day one. The ladder from Notes 01 has more rungs, and we just found the reason to climb.

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

Project 1 is due this week — you've built every piece of it in class, so this is assembly and polish, not a sprint. Submit early, sleep well, and bring questions Tuesday for the last-minute clinic.

Coming up

Sessions 10 and 11 (Oct 6, 8) — Notes 06. Grammars: recipes that grow strings instead of reading them, and the first tool that walks straight through tonight's wall — the counting language falls in the opening minutes. The Project 2 handout comes out 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.