The fundamental challenge in grammatical inference is a tension between succinctness and learnability. While Deterministic Finite Automata (DFAs) are easy to learn because they possess a unique minimal form (the Myhill-Nerode representation), they often suffer from "state explosion," becoming too large to be practical. Conversely, Non-deterministic Finite Automata (NFAs) can be exponentially more compact, but they are notoriously difficult to learn or minimize because they lack a unique canonical structure.
Recent research has converged on Residual Automata and Symbolic Representations as a way to break this deadlock, providing the compactness of non-determinism with the mathematical regularity required for efficient induction.
The Search for Canonical Non-determinism
In the classical view, learning an NFA is "hard" because there is no single "best" NFA for a given language. Benedikt Bollig and colleagues addressed this in Angluin-Style Learning of NFA by focusing on Residual Finite-State Automata (RFSA).
The intuition behind RFSAs is that every state in the automaton should correspond to a "residual" of the language (the set of suffixes that can follow a certain prefix). Unlike general NFAs, RFSAs have a unique minimal form. This allows researchers to adapt Angluin’s $L^*$ algorithm—originally designed for DFAs—to learn non-deterministic models that are significantly more succinct. This concept has been extended even further by Maciej Liskiewicz in Learning Residual Alternating Automata, which demonstrates that alternating automata (which use both AND and OR transitions) can also be learned efficiently if they follow residual properties, offering double-exponential compression over DFAs.
Bridging Neural and Symbolic Logic
A major motivation for this work is the desire to understand what "black box" models, like Recurrent Neural Networks (RNNs) and Transformers, are actually doing. Jordan B. Pollack first suggested in Language Induction by Phase Transition in Dynamical Recognizers that RNNs behave like dynamical systems that undergo "phase transitions" into symbolic logic.
To capture this logic, researchers like Satwik Bhattamishra have developed algorithms like $L^*_{nsp}$ in Automata Learning and Identification of the Support of Language Models. By treating the neural network as an "oracle" that predicts the next symbol, these algorithms can extract a formal DFA that represents the model's underlying grammar. This extraction process is made more robust by using regularization techniques, as shown by Sandra König in Learning minimal automata with recurrent neural networks, which forces the network to converge on a discrete state-space that maps directly to a minimal Mealy machine.
Complexity and the Role of Algebraic Structure
Despite these advances, the field must constantly grapple with the fact that finding the absolute smallest automaton consistent with data is NP-hard. Rajesh Parekh and Vasant G Honavar argue in Learning DFA from Simple Examples that we can only bypass this complexity by assuming the data comes from a "simple" distribution (based on Kolmogorov complexity) or by leveraging specific algebraic properties.
One such property is chain length. Christian Bessiere demonstrated in Chain Length and CSPs Learnable with Few Queries that if the underlying constraint language has a bounded "chain length," the number of queries needed to learn the system drops from exponential to quasi-linear. Similarly, Artem Kaznatcheev showed in Weighted automata are compact and actively learnable that moving from Boolean logic to linear algebra (weighted automata over $\mathbb{Z}_2$) can make compact models efficiently learnable through matrix decomposition, even when the equivalent NFA problem remains PSPACE-complete.
Scaling to Symbolic and Infinite Alphabets
Finally, modern induction must move beyond small, finite alphabets to handle real-world program analysis. George Argyros and Loris D'Antoni introduced the $MAT^*$ algorithm in The Learnability of Symbolic Automata to learn Symbolic Automata.
In these models, transitions are not labeled with single characters but with symbolic predicates (e.g., "any integer > 10"). The key insight here is that the learnability of the entire state machine is strictly tied to the learnability of the underlying logic used for the predicates. By decomposing the problem this way, they allow for the induction of complex systems that operate over infinite domains, bridging the gap between formal language theory and practical software verification.