# LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 6 Aug 2024.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [Using Large Language Models to Automate and Expedite Reinforcement Learning with Reward Machine](https://mlsanity.com/paper/2402.07069/) (2024)

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

- [Rubric-Guided Process Reward for Stepwise Model Routing](https://mlsanity.com/paper/2605.29310/) (2026)
- [Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning](https://mlsanity.com/paper/2606.16576/) (2026)
- [Self-Correction Can Amplify Hallucinations: Fact-Level Repair with Graph-Based Evidence Routing in Multimodal Generation](https://mlsanity.com/paper/2606.00232/) (2026)

## Abstract (arXiv)

The emergence of intelligence in large language models (LLMs) has inspired investigations into their integration into automata learning. This paper introduces the probabilistic Minimally Adequate Teacher (pMAT) formulation, which leverages a probabilistic oracle that could give persistent errors randomly during answering the membership queries for deterministic finite automata (DFA) learning. Given the tendency of LLMs to produce hallucinatory content, we have developed techniques to improve answer accuracy and ensure the correctness of the learned automata. We propose the mathttDiscrimination prompt as well as the mathttVerification prompt and explore their advantages over common prompts. Additionally, we compare DFA learning performance between the TTT algorithm and common active learning algorithms. To address the exponential number of persistent errors, we implement a dynamic query cache refinement algorithm that identifies and corrects conflicting queries by combining the active and passive learning algorithms. The empirical results demonstrate the robustness and efficiency of our approach, providing a theoretical foundation for automata learning with LLMs in the loop.