Finite-State Machine Learning

A finite-state machine (finite automaton) is a model of computation with a finite set of states, an input alphabet, a transition function that says which state follows each symbol, a start state and accepting states. Kleene proved in 1956 that such automata recognise exactly the regular languages. Designing one by hand, fixing its states and transitions, is routine in compilers, network protocols and industrial control.

Finite-state machine learning is a different task: it is not about programming the automaton but about inferring it from data. This is the subject of grammatical inference, and conflating the two, using a pre-built FSM and learning one, is the core error this entry corrects.

What it means to learn an automaton

Learning an FSM means recovering its states and transitions from examples of the behaviour it must capture: strings the system accepts and strings it rejects, or logs of observed sequences. The target is usually the minimal deterministic automaton consistent with that data, because it is the simplest and generalises best. The state structure is not assumed known; discovering that structure is the whole point.

Learning versus designing: two distinct problems

There are two settings. In passive learning the learner receives a fixed set of labelled examples. Gold showed in 1978 that finding the smallest automaton consistent with a set of positive and negative examples is NP-complete: on its own, no efficient algorithm is known. In active learning the learner questions an oracle. Dana Angluin's L* algorithm (1987) learns a deterministic finite automaton in polynomial time using two kinds of query to a «minimally adequate teacher»: membership queries («does the system accept this string?») and equivalence queries («is this automaton correct, and if not, give me a counterexample»). The gap in difficulty between the two settings is central, and the original article ignored it.

Automata and neural networks: relation and limits

The link between automata and neural networks is old: Kleene, building on the McCulloch-Pitts neuron, already showed that finite nets correspond to finite automata. But the equivalence with modern architectures is not unconditional. An idealised RNN with unbounded precision is Turing-complete (Siegelmann and Sontag, 1992); under real finite precision it collapses to finite-state behaviour. Being able to implement an automaton is not the same as being one. Weiss, Goldberg and Yahav (2018) exploited this relation: using L* with the trained RNN as an approximate oracle, they extract an automaton that describes its dynamics; that automaton approximates the network rather than matching it. Presenting RNNs, LSTMs, Transformers and the Differentiable Neural Computer as functional equivalents of an FSM, as the previous version did, is wrong: Transformers have no recurrent state and work over a bounded context window, and DeepMind's DNC (Graves and others, 2016) adds an external memory precisely to exceed the finite-memory limit, so it is not a learnable FSM. It remains open when, and with what guarantees, a neural network admits a faithful description as a finite automaton.