Finite Automaton

A finite automaton is a machine with a fixed, finite set of states that reads a string one symbol at a time and decides whether to accept it. It has no memory beyond which state it is in. Despite that limit, finite automata recognize exactly the languages describable by regular expressions, which makes them the standard engine behind pattern matching and, more recently, behind rules that restrict what a language model may generate.

Definition

A deterministic finite automaton (DFA) consists of:

• a finite set of states \(Q\);
• an alphabet \(\Sigma\) of input symbols (for example, characters);
• a transition function \(\delta: Q\times\Sigma\rightharpoonup Q\), saying which state to move to when a symbol is read in a state. Here it is allowed to be a partial function: where \(\delta\) is undefined for a pair, the string is rejected. A textbook DFA with a total function gets the same effect by sending every missing transition to a non-accepting dead state;
• a start state \(q_0\in Q\);
• a set of accepting states \(F\subseteq Q\).

The machine begins in \(q_0\), applies \(\delta\) for each symbol in order, and accepts the string if it ends in a state in \(F\). “Deterministic” means that from a given state and symbol there is at most one next state, so the path is fully determined by the input.

A traced example

The regular expression -?[0-9]+ matches an optional minus sign followed by one or more digits. A DFA has three states: state 0 (start), state 1 (a minus sign has been read), and state 2 (at least one digit has been read, accepting). Transitions: from 0, - goes to 1 and a digit goes to 2; from 1, a digit goes to 2; from 2, a digit stays in 2. Any other symbol has no transition, so \(\delta\) is partial in this example; a total version would send those symbols to a non-accepting dead state.

Running a program on five inputs gives:

input	states visited	accepted
-42	0, 1, 2, 2	yes
7	0, 2	yes
-	0, 1	no (ends in a non-accepting state)
4-2	0, 2, then no transition	no
empty string	0	no

Two ways to reject appear: running out of valid transitions, and ending in a non-accepting state. The second kind is what matters for generation: the string - is not yet acceptable but can still become so, while 4-2 can never become acceptable.

From automaton to token mask

A language model produces tokens, which are often several characters long, not single characters. To restrict generation to the strings the DFA accepts, push each vocabulary token’s characters through the DFA from the current state. A token is allowed if all of its characters have transitions and its destination state can still reach an accepting state through some continuation. A non-accepting dead state may have transitions but cannot complete a valid string. In the number DFA below, every state with valid outgoing transitions can reach acceptance. A special end-of-sequence token is allowed only when the state is accepting.

For the number DFA and a small hypothetical vocabulary -, 0, 7, 42, -4, 4-, abc, <eos>, the program computes:

• state 0 allows -, 0, 7, 42, -4;
• state 1 allows 0, 7, 42;
• state 2 allows 0, 7, 42, <eos>.

The tokens 4- and abc are never allowed, since their characters leave the language; -4 is allowed only at the start. Precomputing this table once per DFA state turns each generation step into a lookup, which is the idea behind finite-state constrained generation (see Constrained Decoding).

What a finite automaton cannot do

Because it only remembers its current state, a DFA cannot count without bound. It cannot check that parentheses or braces match to arbitrary depth, so it cannot recognize all of JSON, where objects nest inside arrays inside objects. That needs a pushdown automaton (a finite automaton plus a stack), which corresponds to context-free grammars. A DFA can enforce a fixed-depth shape, such as one flat object with known keys, since a fixed number of states suffices.

Related terms

• Nondeterministic finite automaton (NFA) allows several possible next states. It recognizes the same languages as DFAs, and any NFA can be converted to a DFA, sometimes with exponentially more states.
• Regular expression is a notation; the automaton is the machine that executes it. Many regex engines add features (backreferences) that go beyond regular languages.

References

• Willard and Louf, Efficient Guided Generation for Large Language Models (finite-state token masking in practice) — https://arxiv.org/abs/2307.09702