Finite Memory and What It Cannot Recognise

Start with the weakest interesting machine. It reads an input string one symbol at a time, left to right, never going back. It has a fixed, finite set of states, and a transition rule that says: in state q, on symbol a, go to state q'. When the input ends, the machine either sits in an accepting state or it does not.

That is a deterministic finite automaton, or DFA. The entire memory of the machine is which state it is currently in. There is no counter, no stack, no scratch space. If the machine has 12 states, then at every moment it can be in one of 12 situations, and everything it has read so far has been compressed into that single fact.

The set of strings it accepts is called the language the machine recognises.

Finite automata come in a nondeterministic flavour too. An NFA may have several legal moves on the same symbol, and accepts if any path through its choices ends in an accepting state. That sounds strictly more powerful. It is not.

Rabin and Scott proved the equivalence in "Finite Automata and Their Decision Problems", IBM Journal of Research and Development, volume 3, issue 2, pages 114 to 125, 1959. Their subset construction builds a DFA whose states are sets of NFA states, tracking every branch at once. The cost is size: an n-state NFA can require 2^n DFA states.

Kleene had already tied the same class to notation, in "Representation of Events in Nerve Nets and Finite Automata", published in Automata Studies, Princeton University Press, 1956, pages 3 to 41. Regular expressions, NFAs and DFAs all describe exactly the same family: the regular languages.

Finite memory is less limiting than it sounds. Read a binary number most significant bit first. Reading a bit shifts the value left and adds the bit, so the remainder modulo 3 updates by r = (2*r + bit) % 3. Three remainders, three states, and the machine accepts when it ends on remainder zero.

TRANSITION = {(r, b): (2 * r + b) % 3
              for r in (0, 1, 2) for b in (0, 1)}

def divisible_by_three(bits):
    state = 0                       # the only memory there is
    for b in bits:
        state = TRANSITION[(state, b)]
    return state == 0               # 0 is the accepting state

divisible_by_three([1, 1, 0])       # 6  -> True
divisible_by_three([1, 1, 1])       # 7  -> False

Note what is absent: the number itself is never stored. A 900-bit input is checked in constant space.

Now the wall. Consider the language of strings a^n b^n: some number of a's followed by exactly the same number of b's. No finite automaton recognises it, and the proof needs nothing but counting.

Suppose a machine with k states accepts this language. Feed it the k+1 strings a, aa, aaa, up to a^(k+1), and note the state it reaches after each. There are k+1 prefixes and only k states, so by the pigeonhole principle two different prefixes, a^i and a^j with i not equal to j, land the machine in the same state.

From that state the machine's future behaviour is fixed. So it treats a^i b^i and a^j b^i identically. The first must be accepted and the second must be rejected. A single machine cannot do both.

The shape of this argument matters more than the example. It never inspects the machine's design, so no clever construction escapes it. It only uses the fact that the number of states is a constant fixed in advance, while the number of situations the language requires the machine to distinguish grows without bound.

Every impossibility result in this cursus has the same skeleton: identify a quantity the machine must track, show that the machine's resources are bounded, and show the language demands more distinctions than the resources allow. Later the resource is a stack, then a tape, and finally time itself.

The counting argument proves specific languages impossible. A stronger result says exactly which languages are possible.

Call two strings distinguishable if some suffix sends one into the language and the other out of it. Group all strings so that indistinguishable strings sit together. The Myhill-Nerode theorem, whose automaton half Nerode gave in "Linear Automaton Transformations", Proceedings of the American Mathematical Society, volume 9, 1958, pages 541 to 544, says: a language is regular if and only if this grouping produces finitely many groups. The minimal DFA has exactly one state per group.

This converts a vague question into a countable one. For a^n b^n, every a^i is distinguishable from every a^j, so there are infinitely many groups and no DFA. The theorem also explains why minimisation is well defined: the smallest machine is unique.

A practical trap sits here. The pattern languages shipped in Perl, Python, Java and JavaScript are called regular expressions, but several of their features leave the regular class outright.

The clearest is the backreference. The pattern (a+)b\1 matches some a's, then b, then the same run of a's again. That is a counting requirement, so by the argument above no finite automaton accepts it. An engine supporting backreferences therefore cannot compile the pattern into a DFA and run it in one linear pass. It falls back to backtracking search.

That is the mechanism behind catastrophic backtracking, where a pattern like (a+)+b on a long run of a's explores exponentially many splits. The feature is not slow because the implementation is careless. It is slow because the pattern is no longer regular.

The lesson Lexical Analysis: Source to Tokens builds a scanner out of exactly this machinery, and the choice is deliberate rather than historical.

Token shapes are chosen to be regular. An identifier, a number literal, a keyword: each is a pattern with no counting in it, so the scanner is a DFA and runs in one linear pass with constant memory. Nesting is then handed to the next phase.

That split is forced by the result above. Balanced brackets are the canonical non-regular language, so no scanner can match them, and a language design that required the lexer to track nesting would forfeit the linear-time guarantee. The phase boundary in a compiler is not an engineering convention. It sits exactly where finite memory stops being sufficient.

The boundary, in the form worth remembering:

The pattern in the right column is the same every time. A language is regular exactly when the amount that must be carried forward is capped by a constant chosen before the input is seen.

The fix is obvious: give the machine somewhere to put the count. The next lesson adds a stack, and then a tape, and watches what each purchase buys.