Finite Automata

The Advanced Algorithms course deliberately left two questions open. In the traveling salesman and Hamiltonian path lessons, the question “why is this problem hard” was referred to this course in a dedicated section each; the course’s closing then asked: for some problems, is not knowing anything better than brute force a fact about our knowledge, or about the problems themselves. Both debts look at the same place. The first asks about the difficulty of a single problem, the second about where difficulty stands in general. That course’s final measurement showed that testing a candidate path costs 11 steps, while showing that no such path exists costs an average of 11,601 steps — and as was stated plainly there, this was an observation, not a proof. Naming the observation and saying where it turns into a proof is this course’s job.

This course is not a speed course. What it asks is not how many steps a procedure spends, but what a model can never do at all. But a theory’s results cannot be proved by running them. This is why what is measured here is not the theory itself, but what a finite budget can and cannot say. In every lesson, three numbers sit side by side: the budget, what the budget answers, and what it fails to answer. The course’s rule follows from this: a result’s number is written together with its budget, and an unsolvability claim whose budget is not written counts as unmeasured. A finite run never says “this language cannot be recognized” anywhere; it can only say it was not recognized for this k.

State Count as Budget

The first model is the one that has the least. A finite automaton reads its input once, from left to right, keeps nothing it has read, and sits in only one of a finite number of states at any time. It has no memory; the state count takes memory’s place. The definition of a state machine was established in the Software Architecture and Modeling and Representation courses and is not repeated here; the question here is different: how many languages can be recognized.

• MC1 — The alphabet has two symbols. The universe is the finite set of all strings not exceeding a given length limit, and the empty string is in the universe. The universe of strings not exceeding length 4 contains 31 strings.
• MC2 — A language is a subset of the universe. The number of languages that can be written over a 31-string universe is $2^{31}$.
• MC3 — The automaton is built deterministic: the start state is 0, the transition table assigns a single state to every state-symbol pair, and the accepting set is a subset of the states. A string is recognized if the state reached after reading it is in the accepting set.
• MC4 — All k-state automata can be counted: the combination of $k^{2k}$ transition tables with $2^k$ accepting sets. 2 automata for k=1, 64 for k=2, 5832 for k=3.
• MC5 — The measure is an exhaustive count: there is no estimate, no sampling. No measurement in this course uses random or time; what is measured is steps, not duration.

A concrete example settles the definition. A two-state automaton can hold the answer to “is the number of a’s read so far even” in its state: every a flips the state, every b leaves it as it is, and the accepting set is the even state. This automaton neither stores the input nor reads it back; yet it correctly classifies every string of every length. This is what it means to recognize a language: deciding whether a string is in the language, with finite memory and a single pass.

"""Finite automaton: ALL k-state automata are counted, the languages they recognize
are collected."""
from itertools import product

ALPHABET = ("a", "b")


def strings(max_length):
    output = [""]
    for n in range(1, max_length + 1):
        output += ["".join(d) for d in product(ALPHABET, repeat=n)]
    return output


def run_automaton(transitions, accepting, string, start=0):
    state = start
    for symbol in string:
        state = transitions[(state, symbol)]
    return state in accepting


def automata(k):
    """All k-state deterministic automata: transition table x accepting set."""
    cells = [(state, symbol) for state in range(k) for symbol in ALPHABET]
    for targets in product(range(k), repeat=len(cells)):
        transitions = dict(zip(cells, targets))
        for accept_mask in range(1 << k):
            accepting = {i for i in range(k) if accept_mask >> i & 1}
            yield transitions, accepting


def recognizable_languages(k, universe):
    """The number of DISTINCT languages recognized by k-state automata over the universe."""
    languages = set()
    for transitions, accepting in automata(k):
        languages.add(frozenset(s for s in universe if run_automaton(transitions, accepting, s)))
    return languages


U = strings(4)
print("universe: number of strings not exceeding length 4 =", len(U))
print("states  automata  distinct languages  share of universe's writable languages")
for k in (1, 2, 3):
    languages = recognizable_languages(k, U)
    print(f"  {k:3d}  {sum(1 for _ in automata(k)):6d}  {len(languages):16d}"
          f"  {len(languages) / 2 ** len(U):.10f}")
print("total number of languages writable over the universe: 2^31 =", 2 ** 31)

universe: number of strings not exceeding length 4 = 31
states  automata  distinct languages  share of universe's writable languages
    1       2                 2  0.0000000009
    2      64                26  0.0000000121
    3    5832              1054  0.0000004908
total number of languages writable over the universe: 2^31 = 2147483648

Three numbers side by side. Budget: state count 1, 2, 3 — 2, 64, and 5832 automata respectively. What the budget answers: these automata settle 2, 26, and 1054 distinct languages over the 31-string universe. What the budget fails to answer: $2^{31} - 1054$ languages remain; the three-state budget’s share is 0.0000004908.

As the budget rises to 5832 automata, the recognized-language count rises from 2 to 1054, a 527-fold increase. The covered share, by contrast, rises from one in a billion to half in a million. The model class grows, and the ratio is still close to zero. The second point worth noting is that 5832 automata produce only 1054 distinct languages: most automata are copies of one another, because unreachable states and equivalent states rewrite the same language.

What Changes as the Budget Grows

The ratio above was measured in a single universe, and a ratio measured in a single universe is not a result. A budget sweep is mandatory in this course: every measurement is repeated at at least three budget values, and whether the result changes with the budget is recorded. The second axis swept here is the universe’s length limit.

• MC6 — The budget sweep is done along two axes: state count and the universe’s length limit. A budget’s adequacy can only be read once both are written together.

"""Budget sweep: as the universe grows, how much does the same state budget cover."""
from itertools import product

ALPHABET = ("a", "b")


def strings(max_length):
    output = [""]
    for n in range(1, max_length + 1):
        output += ["".join(d) for d in product(ALPHABET, repeat=n)]
    return output


def run_automaton(transitions, accepting, string):
    state = 0
    for symbol in string:
        state = transitions[(state, symbol)]
    return state in accepting


def automata(k):
    cells = [(state, symbol) for state in range(k) for symbol in ALPHABET]
    for targets in product(range(k), repeat=len(cells)):
        transitions = dict(zip(cells, targets))
        for accept_mask in range(1 << k):
            yield transitions, {i for i in range(k) if accept_mask >> i & 1}


def recognizable_languages(k, universe):
    return {frozenset(s for s in universe if run_automaton(transitions, accepting, s))
            for transitions, accepting in automata(k)}


print("length  strings  k=1  k=2   k=3  languages in universe  share k=3 covers")
for length in (1, 2, 3, 4):
    U = strings(length)
    counts = [len(recognizable_languages(k, U)) for k in (1, 2, 3)]
    print(f"{length:6d}  {len(U):7d}  {counts[0]:3d}  {counts[1]:3d}  {counts[2]:4d}"
          f"  {2 ** len(U):20d}  {counts[2] / 2 ** len(U):.10f}")

length  strings  k=1  k=2   k=3  languages in universe  share k=3 covers
     1        3    2    8     8                     8  1.0000000000
     2        7    2   26   116                   128  0.9062500000
     3       15    2   26   690                 32768  0.0210571289
     4       31    2   26  1054            2147483648  0.0000004908

This table is a lesson’s result on its own. In the three-string universe with length limit 1, three-state automata recognize every language: the covered share is 1.0000000000. At length 2 the share is 0.9062500000, at length 3 it is 0.0210571289, at length 4 it is 0.0000004908. Same budget, same model, four measurements — and the whole path between “sufficient” and “nothing.” A budget’s adequacy is not a property of the budget; it is a relationship between the budget and the universe.

The second column is even more instructive. Two-state automata recognize 26 languages at length 2, and still 26 at lengths 3 and 4. As the universe rises from 7 strings to 31, the recognized-language count does not move at all. This saturation is not a measurement flaw: because the number of distinguishable states with two states is exhausted, every new string added to the universe falls into one of the 26 languages that already exist. Growing the budget sometimes changes everything, sometimes nothing; and which one it is can only be seen by measuring.

How Many States Are Needed to Recognize a Language

Until now the question was “how many languages does k states recognize.” The reverse is more useful: how many states, at minimum, does a given language require. The tool for this is the residual language: which suffixes, after a given prefix, put the string into the language. If two prefixes carry the same residual language, no automaton is required to separate them; if they carry different residual languages, an automaton is required to put them in different states. The count of distinct residual languages is called a distinguishability class.

• MC7 — A prefix’s residual language is the set of suffixes in the universe that, when appended after that prefix, put the string into the language.
• MC8 — Only a suffix whose both extensions stay in the universe can separate two prefixes. A suffix that goes past the length limit does not force the automaton into anything.
• MC9 — The exhaustive count is made cheaper here: accepting sets are not scanned separately; once a transition table is given, the accepting decision each string requires is collected, and if no conflict arises, that table suffices. The result is the same as trying accepting sets one by one.

"""Residual language, distinguishability class, and exhaustive count side by side."""
from itertools import product

ALPHABET = ("a", "b")


def strings(max_length):
    output = [""]
    for n in range(1, max_length + 1):
        output += ["".join(d) for d in product(ALPHABET, repeat=n)]
    return output


def residual_language(prefix, target, universe):
    """Which suffixes, after the prefix, put the string into the language."""
    return frozenset(s for s in universe if prefix + s in target)


def distinguishability_classes(target, universe):
    """Shared definition's tool: the number of distinguishability classes."""
    prefixes = {s[:i] for s in universe for i in range(len(s) + 1)}
    return len({residual_language(p, target, universe) for p in prefixes})


def separated_prefixes(target, universe):
    """Only a suffix whose BOTH extensions stay in the universe can separate two prefixes."""
    universe_set = set(universe)
    prefixes = sorted({s[:i] for s in universe for i in range(len(s) + 1)},
                       key=lambda p: (len(p), p))
    signature = {p: tuple((1 if p + s in target else 0) if p + s in universe_set else -1
                           for s in universe) for p in prefixes}
    selected = []
    for p in prefixes:
        if all(any(x >= 0 and y >= 0 and x != y
                   for x, y in zip(signature[p], signature[q])) for q in selected):
            selected.append(p)
    return len(selected)


def recognizer_exists(k, target, universe):
    """All k-state transition tables are scanned; the accepting set is chosen for consistency."""
    cells = [(state, symbol) for state in range(k) for symbol in ALPHABET]
    for targets in product(range(k), repeat=len(cells)):
        transitions = dict(zip(cells, targets))
        required, consistent = {}, True
        for s in universe:
            state = 0
            for symbol in s:
                state = transitions[(state, symbol)]
            wanted = s in target
            if required.setdefault(state, wanted) != wanted:
                consistent = False
                break
        if consistent:
            return True
    return False


def smallest_k(target, universe, upper=5):
    for k in range(1, upper + 1):
        if recognizer_exists(k, target, universe):
            return k
    return None


def even_a(s):
    return s.count("a") % 2 == 0


def ends_with_ab(s):
    return s.endswith("ab")


print("language        length  strings  class  separated prefix  exhaustive")
for name, predicate in (("even a's     ", even_a), ("ends with ab ", ends_with_ab)):
    for length in (2, 3, 4):
        U = strings(length)
        target = frozenset(s for s in U if predicate(s))
        print(f"{name}  {length:7d}  {len(U):4d}  {distinguishability_classes(target, U):4d}"
              f"  {separated_prefixes(target, U):12d}  {smallest_k(target, U):9d}")

language        length  strings  class  separated prefix  exhaustive
even a's             2     7     5             2          2
even a's             3    15     7             2          2
even a's             4    31     9             2          2
ends with ab         2     7     4             3          3
ends with ab         3    15     6             3          3
ends with ab         4    31     9             3          3

Three columns say three separate things, and two of them correct each other. The class count grows as 5, 7, 9 for the “even a’s” language; yet the exhaustive count shows that an automaton exists that recognizes the same language with two states. The difference comes from the universe’s cutoff: prefixes close to the length limit get artificially separated because their suffixes run past the edge of the universe. The class count is an over-count and cannot be read as the state count on its own. The separated-prefix count accounts for this cutoff and matches the exhaustive count exactly in all six measurements — this is an agreement, not a proof, and the budget it was tested at goes up to length limit 4.

This correction is the course’s own rule applied to itself. Class counting is a cheap calculation and the exhaustive count is expensive; whether the cheap calculation stands in for the expensive one is not assumed, it is tested. The same path is followed in the next three lessons: the cheap measure is written first, then compared against the exhaustive count within a budget, and where it diverges is not hidden.

The concept of a regular language is established here not by definition but by measurement. A language is regular if the required state count does not grow as the universe grows: “even a’s” stays at 2 across all three universes, “ends with ab” stays at 3. For these two languages a fixed budget can be chosen, and the chosen budget suffices at every length. The next lesson applies the same three measures to a language that does not carry this property.

Summary

• A finite automaton’s budget is its state count; all k-state deterministic automata can be counted, and there are 2, 64, and 5832 of them for k=1, 2, 3 respectively.
• Over the 31-string universe of length at most 4, these automata recognize 2, 26, and 1054 distinct languages; the number of languages writable over the universe is 2 to the 31, and three states cover a share of 0.0000004908.
• The budget sweep shows that a budget’s adequacy depends on the universe: three states cover the whole universe at length limit 1, and half in a million at length limit 4.
• The number of languages two-state automata recognize freezes at 26 past length 2; growing the universe changes nothing for this budget.
• The count of residual-language classes is an over-count: for “even a’s” the class count comes out to 9, while the exhaustive count shows two states suffice; both extensions of a distinguishing suffix must stay in the universe.
• A language is regular if the required state count does not grow with the universe; it stays constant across all three universes for these two languages.

Next Step

The next lesson applies the same three measures to a language that requires counting: strings with an equal number of a’s followed by an equal number of b’s. What will be asked is this: if the required state count grows with the universe, is growing the budget a solution, or is it not the budget but the model class that needs to change. The answer comes when a three-line production rule does what an entire family of automata cannot.