# A Survey of Neural Networks and Formal Languages

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2020.

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

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Counting Ability of Large Language Models and Impact of Tokenization](https://mlsanity.com/paper/2410.19730/) (2024)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits](https://mlsanity.com/paper/2505.14178/) (2025)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)
- [State space models can express n-gram languages](https://mlsanity.com/paper/2306.17184/) (2023)
- [Extracting Moore Machines from Transformers using Queries and Counterexamples](https://mlsanity.com/paper/2410.06045/) (2024)
- [Emergent Stack Representations in Modeling Counter Languages Using Transformers](https://mlsanity.com/paper/2502.01432/) (2025)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)
- [Exploring Major Transitions in the Evolution of Biological Cognition With Artificial Neural Networks](https://mlsanity.com/paper/2509.13968/) (2025)
- [On the Expressive Power of Transformers](https://mlsanity.com/paper/2608.12671/) (2026)

## Abstract (arXiv)

This report is a survey of the relationships between various state-of-the-art neural network architectures and formal languages as, for example, structured by the Chomsky Language Hierarchy. Of particular interest are the abilities of a neural architecture to represent, recognize and generate words from a specific language by learning from samples of the language.