# Learning Context-Free Languages with Nondeterministic Stack RNNs

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

## Key facts

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

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

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)
- [Beam Tree Recursive Cells](https://mlsanity.com/paper/2305.19999/) (2023)
- [Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability](https://mlsanity.com/paper/2311.04449/) (2023)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [Algorithms for Weighted Pushdown Automata](https://mlsanity.com/paper/2210.06884/) (2022)
- [Bearing Syntactic Fruit with Stack-Augmented Neural Networks](https://mlsanity.com/paper/2511.03547/) (2025)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)
- [Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts](https://mlsanity.com/paper/2607.29496/) (2026)

## Abstract (arXiv)

We present a differentiable stack data structure that simultaneously and tractably encodes an exponential number of stack configurations, based on Lang's algorithm for simulating nondeterministic pushdown automata. We call the combination of this data structure with a recurrent neural network (RNN) controller a Nondeterministic Stack RNN. We compare our model against existing stack RNNs on various formal languages, demonstrating that our model converges more reliably to algorithmic behavior on deterministic tasks, and achieves lower cross-entropy on inherently nondeterministic tasks.