Extracting a finite-state machine from data seems like it should be straightforward. If we observe a system's behavior over time, we ought to be able to map its internal states and transitions. Yet, automata induction—the process of learning the underlying rules of a formal grammar or state machine from examples—is one of the most notoriously intractable problems in computer science.
To understand why this problem is so difficult, and how modern machine learning circumvents it, we must look at the combinatorial bottlenecks of state spaces, the price of non-determinism, and the structural workarounds that make learning possible.
The Passive Learning Bottleneck
The core difficulty of automata induction arises in the passive learning setting, where an algorithm must infer a machine solely from a static, fixed dataset of observed behaviors without the ability to actively query the system.
If our only goal were to find any machine that fits our training data, the task would be trivial: we could simply build a giant tree where every observed sequence forms a unique path. However, a tree cannot generalize to infinite-length strings. To generalize, the machine must contain loops, which means we must compress the tree by merging states together.
This is where we hit a mathematical wall. As noted by Vasant G Honavar et al. in Introduction and Aryeh Kontorovich et al. in A Universal Kernel for Learning Regular Languages, finding the minimal Deterministic Finite Automaton (DFA) consistent with a given dataset is an NP-complete problem. Jordan B. Pollack in Language Induction by Phase Transition in Dynamical Recognizers and Anya Belz in Discovering Phonotactic Finite-State Automata by Genetic Search similarly frame this minimality constraint as a fundamental NP-hard barrier.
To build intuition for this hardness, imagine trying to merge two states in a tentative automaton. If you merge state $A$ and state $B$, you are betting that they behave identically for all possible future inputs. If state $A$ eventually leads to an accepting state on some suffix string but state $B$ leads to a rejection, your merge was invalid. Because a single merge can ripple forward and cause downstream contradictions across thousands of examples, finding the globally optimal, minimal configuration of state merges becomes an explosive combinatorial puzzle.
As Sandra König et al. explain in Learning minimal automata with recurrent neural networks, passive learners lack the interactive query capabilities that allow active learning algorithms to systematically resolve these ambiguities. This exact same grammatical bottleneck appears whenever we try to find the minimum number of steps required to assemble any complex structure from basic components, a connection formalized by Christoph Flamm et al. in Assembly in Directed Hypergraphs.
The Non-Determinism and Infinite-Input Barriers
If learning deterministic machines is hard, moving to more expressive models—such as Non-deterministic Finite Automata (NFAs) or automata that process infinite sequences ($\omega$-automata)—compounds the complexity significantly.
Intuitively, NFAs are highly desirable because they can be exponentially more compact than DFAs. In an NFA, a single input can transition a machine into multiple parallel states simultaneously. However, Artem Kaznatcheev et al. point out in Weighted automata are compact and actively learnable that finding a minimal NFA is PSPACE-complete.
The root cause of this leap in complexity is the loss of a canonical form. For any regular language, Myhill-Nerode theory guarantees that there is a unique, mathematically distinct minimal DFA. This gives learning algorithms a clear target. NFAs, by contrast, lack a unique minimal representation; multiple completely different structural configurations can represent the exact same language. Without a canonical target, a learning algorithm cannot easily determine if it is making progress toward the most efficient model. Maciej Liskiewicz et al. address this in Learning Residual Alternating Automata by designing algorithms for specific subclasses like Residual Alternating Finite Automata (RAFAs) to recapture some structural predictability.
This barrier becomes even more pronounced when dealing with infinite-duration systems via $\omega$-automata. Dana Fisman in Polynomial Identification of ømega-Automata demonstrates that learning non-deterministic $\omega$-automata is fundamentally impossible within polynomial time and data constraints, requiring an exponential number of examples just to tell similar languages apart. In subsequent work, Dana Fisman in Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages proves that while deterministic $\omega$-automata can be efficiently "taught" using small, concise sets of characteristic examples, non-deterministic variants completely lack these concise sets, presenting an absolute theoretical barrier to efficient learning.
Bypassing Hardness: Average Cases and Richer Supervision
To make automata induction practical, researchers must change the rules of the game. If worst-case arbitrary languages are unlearnable, we can bypass the bottleneck by altering our assumptions about the data distribution or the richness of the feedback.
Shifting to Average-Case and Random Automata
Instead of assuming an adversarial environment, what if the target automaton is chosen at random? Yoav Freund et al. broke the worst-case logjam in Efficient Learning of Typical Finite Automata from Random Walks by combining a worst-case structural model with an average-case random state-labeling scheme, proving that "typical" automata can be learned efficiently from random walks.
Following this paradigm, Dongqu Chen in Learning a Random DFA from Uniform Strings and State Information demonstrated that random DFAs become tractable when strings are sampled uniformly and the learner is granted partial internal state information. To understand why random walks unlock these algorithms, Benjamin Fish et al. in Open Problem: Meeting Times for Learning Random Automata reduced the learning complexity to a question of graph "meeting times"—essentially, how quickly random walks collide on a state graph, providing a geometric bound for tracking down state identities.
Biasing Toward Simplicity
Another strategy alters the data distribution to favor simplicity. Rajesh Parekh et al. in Learning DFA from Simple Examples leveraged Kolmogorov complexity and the Solomonoff-Levin universal distribution to prove that if a teacher provides examples biased toward structural simplicity, the learner can bypass standard PAC-learning hardness bounds and identify the target DFA efficiently.
Leveraging Next Symbol Prediction
In traditional language learning settings, a sequence provides only a single bit of information: it is either accepted or rejected. Modern language modeling, however, operates on a much richer signal: predicting the probability distribution of the very next token.
Traditional Setting: "The quick brown fox" ---> [ ACCEPT ] (1 bit of feedback)
Next Symbol Setting: "The quick brown" ---> [ fox: 80%, dog: 10%, cat: 5%... ] (Dense vector)
Satwik Bhattamishra et al. in The Next Symbol Prediction Problem: PAC-learning and its relation to Language Models proved that regular languages, which are notoriously hard to learn from binary labels, become efficiently PAC-learnable when the algorithm is trained via Next Symbol Prediction (NSP). Because the dense vector of next-symbol probabilities reveals the exact local branching structure of the underlying state, it effectively acts as a map of the automaton's transitions.
However, this leverage has limits. In a subsequent work, Satwik Bhattamishra et al. in Automata Learning and Identification of the Support of Language Models demonstrated that even with information-rich NSP labels, extracting a perfect formal representation remains bounded by cryptographic hardness in the worst case.
Despite this lingering theoretical boundary, the dense supervision of next-token prediction is exactly what allows modern neural architectures to successfully approximate and expose the discrete, underlying logic of complex sequence models in practical applications.
Key Foundational Work
Efficient Learning of Typical Finite Automata from Random Walks (1997) — contributed 2 concept elements to this direction.
Language Induction by Phase Transition in Dynamical Recognizers (1990) — contributed 1 concept elements to this direction.