The Simplest Machine

Last week we agreed that every problem is a language, and that solving a problem means deciding membership in it. Tonight we build the weakest machine that can decide anything at all — and we build it first precisely because it is weak. When a machine can barely do anything, everything it manages to do teaches you something exact.

Start by being the machine yourself. You stand at a conveyor belt. Symbols stream past, left to right, one at a time. You may look at each symbol once — no reaching back, no peeking ahead, no notebook, no pockets. When the belt ends, you must say yes or no, immediately. The only thing you are allowed to carry from one symbol to the next is which mode your mind is in, and you must choose your full repertoire of modes before the belt starts, without knowing how long the input will be.

Could you decide, under those rules, whether the string streaming past has an even number of a's? You could, and you would need exactly two modes: even so far and odd so far. Start in even — zero a's have gone by, and zero is even. Every time an a passes, switch modes. Every time a b passes, stay put. When the belt stops, answer yes exactly when you are standing in even. You never counted; you have no idea whether you saw four a's or four thousand. You remembered one bit, and one bit was enough.

A DFA is not a weak computer. It is an exact answer to the question: what can be noticed in one pass, with a mind fixed in advance?

That is the whole machine. Everything else tonight is bookkeeping: writing the modes down as a formal object, running it on paper and in code, and — the real craft — learning to choose the modes for a language you have never seen before.

Now we write the conveyor-belt game down as a mathematical object, using nothing but the set language from Notes 01 §06. Five parts, always the same five.

Note the type of δ: its domain is the Cartesian product Q × Σ — the set of all (state, symbol) pairs, exactly the product from last week's toolkit — and it is a total function. For every pair, exactly one next state. Not zero: the machine can never jam, never fall off an edge, never encounter a situation with no rule. Not two: the machine never has a choice. Feed a DFA a string and its entire future is fixed before the first symbol arrives. That is what deterministic means, and it is the property we will deliberately give up next week.

Here is the even-a's machine from §01, formally. M₁ = (Q, Σ, δ, q₀, F) with Q = {E, O}, Σ = {a, b}, q₀ = E, F = {E}, and δ given by δ(E, a) = O, δ(E, b) = E, δ(O, a) = E, δ(O, b) = O. Two states, four rules, done. The five-tuple looks like ceremony for something this small — the point of the ceremony is that Project 1 will feed machines to a program, and programs eat tuples, not prose.

Whatever a DFA knows about everything it has read so far, it knows as a single state name. Nothing else survives.

Sit with that for a second, because it is the deepest fact about this machine. After reading half a gigabyte of input, the machine's entire memory of that half gigabyte is: which element of Q it is standing on. If two different prefixes lead to the same state, the machine has permanently forgotten every difference between them — it will treat all possible futures of those two prefixes identically. Every limit we prove about DFAs, from tonight's intuitions to Week 5's pumping lemma, is this one sentence wearing different clothes.

Nobody thinks in five-tuples. There are two standard pictures of a DFA, and you should be fluent in both, because they are good at different jobs.

The state diagram

Circles are states. An arrow from nowhere marks the start state. A double circle marks an accepting state. A labeled arrow from state to state is one rule of δ; several labels on one arrow abbreviate several rules. Here is M₁:

The transition table

The same machine as a table: one row per state, one column per symbol, each cell the next state. By convention we mark the start state with → and accepting states with *.

→ marks the start state; * marks membership in F.

The two views split the work between them. The diagram is for thinking: your eye follows arrows the way the machine follows input, and a wrong design usually looks wrong. The table is for rigor and for code: totality becomes visible — every cell filled, no blanks, no cell holding two names — and the table is, character for character, the dictionary you will type into Python in §08. Design on the diagram; verify and implement on the table.

A computation is a walk. Put a finger on the start state, read the input left to right, and let each symbol push your finger along an arrow. Here is M₁ on the input w = abba:

Read it as a sequence of states: E, then a takes us to O, then b keeps us at O, then b keeps us at O, then a returns us to E. The walk is E → O → O → O → E, it ends in E, and E ∈ F, so M₁ accepts abba — which is right, because abba has two a's. Notice the walk has five states for a four-symbol input: one before any symbol, one after each. A trace always has |w| + 1 entries. Off-by-one bugs in Project 1 almost all come from forgetting the state before the first symbol.

To say this without pictures, we extend δ — which eats one symbol — to a function that eats a whole string. And look at the shape of the definition: it is a definition by induction on length, the exact pattern from Notes 01 §06, now doing load-bearing work.

Two consequences fall straight out of the base case. First, δ̂(q₀, ε) = q₀: a DFA accepts the empty string exactly when its start state is accepting. The machine's verdict on ε is decided before it reads anything, by a single set-membership check — which is why ε belongs first in every test suite you write this term. Second, because each step of the recursion is a total function, δ̂ is total too: every DFA gives a definite verdict on every string over its alphabet. No crashes, no loops, no "it depends." Determinism all the way up.

Now stop reading and run machines. The simulator below has four machines you have met or are about to meet. Type an input, then step through it one symbol at a time. Watch three things move together: the finger on the tape, the state (with what that state means), and the cell of the transition table being consulted. When any two of the three surprise you, that is the lesson.

Every DFA, run over all of Σ*, sorts the strings into two piles — and the yes-pile is a set of strings, which is to say a language. This is where Week 1 and Week 2 click together.

Careful with the direction of this definition. Every DFA recognizes exactly one language. But a language is recognized by many machines — add an unreachable state to M₁ and you have a different DFA with the same language. Machine and language are different kinds of things, and the interesting claims all have the shape "this machine recognizes that language." Which raises the real question: how would you ever prove such a claim?

The claim L(M) = L is an equality of sets, and Notes 01 §06 told you what that costs: two inclusions. Every string in L must be accepted, and every accepted string must be in L. Students reliably argue the first half and skip the second — the machine that accepts everything passes the first half for any L. The working tool for getting both halves at once is the state invariant: attach to each state a sentence describing exactly which prefixes land there, then prove the sentences by induction on prefix length.

Worked correctness argument, the Project 1 model

Claim. L(M₁) = { w ∈ {a,b}* | w has an even number of a's }.

Invariant. For every string w: δ̂(E, w) = E if w has an even number of a's, and δ̂(E, w) = O if odd.

Proof, by induction on |w|. Base: w = ε has zero a's — even — and δ̂(E, ε) = E. ✓ Step: assume the invariant holds for w; consider one more symbol. If it is b: the a-count is unchanged, and δ maps E ↦ E and O ↦ O on b, so both sides stand still — the invariant survives. If it is a: the a-count flips parity, and δ maps E ↦ O and O ↦ E on a, so both sides flip together — the invariant survives. ∎

Conclusion. w ∈ L(M₁) iff δ̂(E, w) ∈ F = {E} iff (by the invariant) w has an even number of a's. Both inclusions at once, because the invariant is an "exactly" statement, not an "if" statement. This construct-then-induct pairing is the skeleton of every correctness argument in Project 1 — write it once tonight by hand and the project's written half stops being scary.

Designing a DFA is answering one question with discipline: what is the least I must remember about the prefix read so far to finish the job, no matter what the future holds? Each distinguishable answer becomes a state. If the set of answers you need is finite, you have a DFA; list the answers, wire the arrows, mark the accepting ones. Four worked constructions, in increasing order of cunning.

1 · "Ends with b" — remember only the last symbol

To know whether the string ends with b, you need to remember exactly one thing: whether the most recent symbol was a b. Two states: N ("last symbol was not b — or there has been no symbol"), B ("last symbol was b"). Every incoming symbol overwrites the memory completely.

Note ε is rejected — N is not accepting — which is correct: the empty string does not end with b.

2 · "Contains bb" — a progress meter with a point of no return

Here the memory is progress toward the goal: no b just seen, one b just seen, bb found. And once bb has been seen, nothing can unsee it — the third state loops to itself on everything. A state all of whose arrows point back at itself is called a trap state; an accepting trap means "the property is permanent."

3 · "Binary numeral divisible by 3" — store the abstraction, not the data

This one looks impossible for a moment: the number a long numeral denotes is astronomically large, and a DFA cannot store it. It does not have to. When you have read a numeral prefix denoting the value v and the next digit is d, the new prefix denotes 2v + d — appending a bit doubles and adds. And (2v + d) mod 3 depends only on v mod 3, not on v. So the remainder is a finite summary of the prefix that is closed under reading one more symbol, and three states suffice: r0, r1, r2, meaning "value so far ≡ 0, 1, 2 (mod 3)." The transition rule is pure arithmetic: δ(rᵢ, d) = r₍₂ᵢ₊d₎ ₘₒd ₃.

Check one row yourself: from r1 (value ≡ 1), reading 0 gives value ≡ 2·1+0 = 2, and reading 1 gives ≡ 3 ≡ 0. The machine is doing modular arithmetic with its feet.

Two honest footnotes. This machine accepts ε and accepts numerals with leading zeros — whether those should count is a specification decision, not a math fact, and tightening the machine to well-formed numerals only costs two more states (a good exercise). And the design generalizes completely: divisibility by k in base b needs exactly k remainder states, for any k and b. A DFA cannot count without bound, but it can do modular arithmetic forever — the difference between those two sentences is the heart of §07.

4 · Two conditions at once — run both machines in parallel

Now a compound language: strings with an even number of a's and ending with b. You could squint for a clever small machine — or notice that you already own a machine for each half, and that one reader can run both at once. Carry a pair of states, one component per machine; feed each incoming symbol to both components independently. The pair (x, y) is a state of a new machine whose state set is the Cartesian product Q₁ × Q₂ — Notes 01 §06 said pairs of states would pay rent, and here they are. Accept when both components are accepting.

For our two machines that is four states: (E,N), (E,B), (O,N), (O,B); the start is (E,N); the accepting set for the intersection is {(E,B)}. Step through it below and watch the components move independently — the a's flip the first coordinate, the b's set the second.

Flip the combiner from intersection to union and watch what changes: nothing about the states or the arrows — only which pair-states count as accepting. {(E,B)} grows to {(E,N), (E,B), (O,B)}. One machine, two languages, distinguished purely by F. This product construction is our first hint that regular languages are closed under ∩ and ∪; Week 4 makes the closure story systematic, and Project 1's converter is where you meet products at scale.

The constructions in §06 might leave the impression that a sufficiently clever choice of states handles anything. It does not, and you can feel exactly where the wall is by trying the canonical language from Notes 01: L = { aⁿbⁿ | n ≥ 0 } — some a's, then equally many b's.

Ask the design question. While reading the a's, what must you remember? The exact count — because the future may demand you check it against any number of b's. Not the count mod 3, not "more than five," the count itself. And the count is unbounded, while your states are fixed in advance. Here is the collision, run at full rigor for a moment. Suppose a DFA with k states claims to recognize L. Feed it the k+1 prefixes a¹, a², …, a^k+1. It has only k states, so two of those prefixes — say aⁱ and aʲ with i ≠ j — land on the same state. But we said it: when two prefixes share a state, the machine has permanently forgotten the difference. From that shared state, reading bⁱ leads to one fixed final state with one fixed verdict. That verdict must be "accept," because aⁱbⁱ ∈ L — and it must be "reject," because aʲbⁱ ∉ L. One state cannot answer twice. The machine was bluffing.

A DFA can count up to any bound you fix in advance. What it cannot do is count without a bound.

Notice the proof pattern — contradiction, with a pigeonhole supplying the collision — straight from the Notes 01 toolkit. In Week 5 this argument gets packaged into a reusable tool, the pumping lemma, which handles a whole family of such proofs without re-deriving the pigeonhole each time. Tonight, carry the intuition: finite states means finite distinctions. A DFA can notice any property that requires only boundedly many distinctions among prefixes — last symbol, progress toward a substring, a remainder, any boolean combination of such things, any finite language. It cannot notice a property that requires unboundedly many — matching counts, balanced brackets, palindromes. When you meet a language in the wild, that is the diagnostic: count the distinctions the past forces you to maintain. Finite? DFA. Unbounded? You have left the first rung, and you will need Week 6's machinery.

The five-tuple translates into Python with almost no friction — that is the payoff of the ceremony in §02. A machine is data: a dictionary whose "delta" entry is exactly the transition table of §03, one nested dict per row.

EVEN_AS = {
    "alphabet": {"a", "b"},
    "states":   {"E", "O"},
    "start":    "E",
    "accept":   {"E"},
    "delta": {
        "E": {"a": "O", "b": "E"},
        "O": {"a": "E", "b": "O"},
    },
}

The simulator is the definition of δ̂ written as a loop instead of a recursion: start at the start state, take one δ-step per symbol, check F at the end. Ten lines, and they are the seed of Project 1.

def run_dfa(m, w):
    """Decide membership of w in L(m). One pass, no lookahead."""
    state = m["start"]
    for ch in w:
        if ch not in m["alphabet"]:
            raise ValueError(f"{ch!r} is not in the alphabet")
        state = m["delta"][state][ch]
    return state in m["accept"]

Two disciplines to adopt on day one. First, validate machines, not just inputs — a hand-written table with a missing cell is not a DFA, and you want the loud failure at load time, not mid-run:

def is_total(m):
    # every (state, symbol) cell filled, with a real state
    return all(
        m["delta"].get(q, {}).get(ch) in m["states"]
        for q in m["states"]
        for ch in m["alphabet"]
    )

Second, make the walk observable. A function that yields the trace — the |w| + 1 states of §04 — costs four lines and repays itself every time a test fails, because a wrong verdict tells you nothing while a wrong walk shows you the exact step where your table disagrees with your intention:

def trace_dfa(m, w):
    state = m["start"]
    yield state
    for ch in w:
        state = m["delta"][state][ch]
        yield state

# ε first, always — then the shortest strings that differ
assert run_dfa(EVEN_AS, "") is True
assert run_dfa(EVEN_AS, "a") is False
assert run_dfa(EVEN_AS, "abba") is True
print(list(trace_dfa(EVEN_AS, "abba")))   # ['E','O','O','O','E']

The Project 1 specification, released this week, asks for exactly this engine behind a small file format, plus NFA support and a converter you will meet on Tuesday. If you type these thirty lines yourself tonight — type, not paste — the project's first milestone is already half done.

Six questions. Answer before you click — being wrong here is free and useful.

The Project 1 specification is released this week on the course repository, and Week 3 builds directly on tonight's machinery — nondeterminism is a small change to the five-tuple with large consequences. Arrive with the following done.

Coming up

Sessions 4 and 5 (Sept 15, 17) — Notes 03. Nondeterministic finite automata: machines allowed to guess, why they are dramatically easier to design, and the subset construction that compiles their guessing away — the algorithm at the center of Project 1. Project 1 work begins in earnest.

If any part of tonight did not land, email me — yair.chaya@liu.edu — or ask for an office-hours slot. Replies within 24 hours.