# L^*LM: Learning Automata from Examples using Natural Language Oracles

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 10 Feb 2024.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting](https://mlsanity.com/paper/2305.04388/) (2023)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [RoboCLIP: One Demonstration is Enough to Learn Robot Policies](https://mlsanity.com/paper/2310.07899/) (2023)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Program Synthesis using Natural Language](https://mlsanity.com/paper/1509.00413/) (2015)
- [Interpretable Apprenticeship Learning with Temporal Logic Specifications](https://mlsanity.com/paper/1710.10532/) (2017)
- [Explaining Multi-stage Tasks by Learning Temporal Logic Formulas from Suboptimal Demonstrations](https://mlsanity.com/paper/2006.02411/) (2020)
- [Automaton-Based Representations of Task Knowledge from Generative Language Models](https://mlsanity.com/paper/2212.01944/) (2022)
- [Predictive Runtime Monitoring for Mobile Robots using Logic-Based Bayesian Intent Inference](https://mlsanity.com/paper/2108.01227/) (2021)
- [Multimodal Pretrained Models for Verifiable Sequential Decision-Making: Planning, Grounding, and Perception](https://mlsanity.com/paper/2308.05295/) (2023)
- [Finite LTL Synthesis with Environment Assumptions and Quality Measures](https://mlsanity.com/paper/1808.10831/) (2018)
- [Symmetry Breaking Predicates for SAT-based DFA Identification](https://mlsanity.com/paper/1602.05028/) (2016)

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

- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning](https://mlsanity.com/paper/2606.16576/) (2026)

## Abstract (arXiv)

Expert demonstrations have proven an easy way to indirectly specify complex tasks. Recent algorithms even support extracting unambiguous formal specifications, e.g. deterministic finite automata (DFA), from demonstrations. Unfortunately, these techniques are generally not sample efficient. In this work, we introduce L^*LM, an algorithm for learning DFAs from both demonstrations and natural language. Due to the expressivity of natural language, we observe a significant improvement in the data efficiency of learning DFAs from expert demonstrations. Technically, L^*LM leverages large language models to answer membership queries about the underlying task. This is then combined with recent techniques for transforming learning from demonstrations into a sequence of labeled example learning problems. In our experiments, we observe the two modalities complement each other, yielding a powerful few-shot learner.