# Representing Formal Languages: A Comparison Between Finite Automata and Recurrent Neural Networks

arXiv: https://arxiv.org/abs/1902.10297 · HTML: https://mlsanity.com/paper/1902.10297/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2019.

## Built on by (most cited first, 9 of 9)

- [Generative learning for nonlinear dynamics](https://mlsanity.com/paper/2311.04128/) (2023)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)
- [Can deep neural networks learn process model structure? An assessment framework and analysis](https://mlsanity.com/paper/2202.11985/) (2022)
- [On the Dynamics of Learning Time-Aware Behavior with Recurrent Neural Networks](https://mlsanity.com/paper/2306.07125/) (2023)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)
- [Integrating Regular Expressions with Neural Networks via DFA](https://mlsanity.com/paper/2109.02882/) (2021)
- [On the Relationship Between RNN Hidden State Vectors and Semantic Ground Truth](https://mlsanity.com/paper/2306.16854/) (2023)
- [When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal](https://mlsanity.com/paper/2607.11953/) (2026)

## Abstract (arXiv)

We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an em abstraction obtained by clustering small sets of MDFA states into "superstates". A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.