# Extracting Moore Machines from Transformers using Queries and Counterexamples

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Transformers without Tears: Improving the Normalization of Self-Attention](https://mlsanity.com/paper/1910.05895/) (2019)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [On Evaluating the Generalization of LSTM Models in Formal Languages](https://mlsanity.com/paper/1811.01001/) (2018)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Learning Product Automata](https://mlsanity.com/paper/1705.02850/) (2017)

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

- [Extracting Robust Register Automata from Neural Networks over Data Sequences](https://mlsanity.com/paper/2511.19100/) (2025)
- [Algorithm Development in Neural Networks: Insights from the Streaming Parity Task](https://mlsanity.com/paper/2507.09897/) (2025)

## Abstract (arXiv)

Fuelled by the popularity of the transformer architecture in deep learning, several works have investigated what formal languages a transformer can learn from data. Nonetheless, existing results remain hard to compare due to methodological differences. To address this, we construct finite state automata as high-level abstractions of transformers trained on regular languages using queries and counterexamples. Concretely, we extract Moore machines, as many training tasks used in literature can be mapped onto them. We demonstrate the usefulness of this approach by studying positive-only learning and the sequence accuracy measure in detail.