# The Neural State Pushdown Automata

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

## Key facts

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

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

- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks](https://mlsanity.com/paper/2309.14691/) (2023)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [An Empirical Analysis of Recurrent Learning Algorithms In Neural Lossy Image Compression Systems](https://mlsanity.com/paper/2201.11782/) (2022)
- [Certifiable Boolean Reasoning Is Universal](https://mlsanity.com/paper/2602.05120/) (2026)
- [Neuro-mimetic Task-free Unsupervised Online Learning with Continual Self-Organizing Maps](https://mlsanity.com/paper/2402.12465/) (2024)
- [Like a bilingual baby: The advantage of visually grounding a bilingual language model](https://mlsanity.com/paper/2210.05487/) (2022)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)
- [Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits](https://mlsanity.com/paper/2602.03970/) (2026)

## Abstract (arXiv)

In order to learn complex grammars, recurrent neural networks (RNNs) require sufficient computational resources to ensure correct grammar recognition. A widely-used approach to expand model capacity would be to couple an RNN to an external memory stack. Here, we introduce a "neural state" pushdown automaton (NSPDA), which consists of a digital stack, instead of an analog one, that is coupled to a neural network state machine. We empirically show its effectiveness in recognizing various context-free grammars (CFGs). First, we develop the underlying mechanics of the proposed higher order recurrent network and its manipulation of a stack as well as how to stably program its underlying pushdown automaton (PDA) to achieve desired finite-state network dynamics. Next, we introduce a noise regularization scheme for higher-order (tensor) networks, to our knowledge the first of its kind, and design an algorithm for improved incremental learning. Finally, we design a method for inserting grammar rules into a NSPDA and empirically show that this prior knowledge improves its training convergence time by an order of magnitude and, in some cases, leads to better generalization. The NSPDA is also compared to a classical analog stack neural network pushdown automaton (NNPDA) as well as a wide array of first and second-order RNNs with and without external memory, trained using different learning algorithms. Our results show that, for Dyck(2) languages, prior rule-based knowledge is critical for optimization convergence and for ensuring generalization to longer sequences at test time. We observe that many RNNs with and without memory, but no prior knowledge, fail to converge and generalize poorly on CFGs.