# On the Ability and Limitations of Transformers to Recognize Formal Languages

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2020.

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

- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2410.13857/) (2024)
- [In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitzness](https://mlsanity.com/paper/2402.11639/) (2024)
- [Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot](https://mlsanity.com/paper/2406.06893/) (2024)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment](https://mlsanity.com/paper/2204.09148/) (2022)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [Looped Transformers with Layer Normalization Provably Learn the Power Method](https://mlsanity.com/paper/2606.00605/) (2026)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)

## Abstract (arXiv)

Transformers have supplanted recurrent models in a large number of NLP tasks. However, the differences in their abilities to model different syntactic properties remain largely unknown. Past works suggest that LSTMs generalize very well on regular languages and have close connections with counter languages. In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so. We first provide a construction of Transformers for a subclass of counter languages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations. In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction. Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known measure of complexity. Our analysis also provides insights on the role of self-attention mechanism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model.