Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks

Shlok Shelat, Jay Raval, Souvik Roy, Manas Gaur · 2026

Read Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks by Shlok Shelat, Jay Raval, Souvik Roy, Manas Gaur (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13392.txt.

Introduction

Shlok Shelat, Jay Raval, Souvik Roy, and Manas Gaur test if language models truly reason or just recall on formal tasks. Such models score well on formal tongue tasks. That score may show true symbol sense or just match of known forms.

Their bench asks models to build finite automata, small state machines, from regular tongues. It holds fact asks and build tasks from public sources. It also holds two kinds of new tasks. Some are hand made with many valid builds. By set of known next to new, the bench splits recall from sense. For AI teams, that split is key to trust on logic tasks.

Catalog record

CREATORShlok Shelat, Jay Raval, Souvik Roy, Manas Gaur
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-13392

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks Shlok Shelat, Jay Raval, Souvik Roy, Manas Gaur Abstract Large language models (LLMs) have demonstrated strong performance on formal language tasks, yet whether this reflects genuine symbolic reasoning or pattern matching on familiar constructions remains unclear. We introduce a benchmark for deterministic finite automata (DFA) construction from regular languages, comprising factual knowledge questions, seen construction problems from public sources, and two types of unseen problems: hand-crafted instances with multiple interacting constraints and systematically generated problems via Arden’s theorem. Models achieve perfect accuracy on factual questions and 84-90% on seen tasks. However, accuracy drops sharply on unseen problems (by 30-64%), with failures stemming from systematic misinterpretation of language constraints, incorrect handling of Kleene-star semantics, and a failure to preserve global consistency. We evaluate a three-stage hint protocol that enables correction of shallow errors but does not reliably resolve globally inconsistent or structurally flawed automata. Our analysis across multiple prompting strategies (direct, Chain-of-Thought, Tree-of-Thought) reveals that errors persist regardless of prompting approach, exposing a fundamental gap between LLMs’ ability to generate syntactically plausible DFAs and their capacity for semantically correct formal reasoning. 1 Introduction Large language models (LLMs) have demonstrated remarkable performance on diverse reasoning benchmarks, from mathematical problem-solving 7 ; 10 ; 2 to code generation 11 . However, a fundamental question remains unresolved: do these models perform genuine symbolic reasoning, or do they primarily rely on pattern matching over memorized examples? Recent work reveals persistent failures on tasks requiring structured symbolic manipulation 5 ; 13 , suggesting that strong benchmark performance may not reflect robust reasoning capabilities. We address this question through the lens of deterministic finite automata (DFA) construction from regular languages , a core problem in the Theory of Computation (ToC). Moreover, this also depicts the task of lexical analyser which are solved by using tools like Lex, Flex with limitations 1 . This task offers unique advantages as a reasoning probe: (1) correctness is formally verifiable through exhaustive testing, (2) solutions require multi-step symbolic manipulation with global consistency constraints, (3) the space of possible problem instances is combinatorially vast, and (4) DFAs represent the simplest non-trivial computational model, ensuring that failures cannot be attributed to problem complexity or ambiguous specifications. We focus on prompting-based evaluation (rather than fine-tuning) to reflect practical LLM usage. Critically, while existing ToC benchmarks 3 ; 14 evaluate factual knowledge and proof verification, they do not systematically control for memorization versus compositional generalization , a model may succeed by recalling similar problems from training data rather than reasoning from first principles. To isolate genuine reasoning capability, we introduce a carefully designed benchmark with three components: (1) a knowledge-checking dataset verifying mastery of DFA definitions and properties, (2) a seen construction dataset comprising 90 publicly available DFA problems, and (3) an unseen construction dataset with 180 novel problems generated via two complementary approaches. The first approach, mathematical art , manually constructs problems with multiple interacting constraints, forbidden substrings, and narrative-based specifications (e.g., encoding chess moves). The second approach, mathematical engineering , systematically generates problems via Arden’s theorem 8 , producing structurally complex regular expressions unlikely to appear in training data. This seen/unseen split enables us to measure the performance gap attributable to memorization versus reasoning. We evaluate frontier LLMs: GPT-5.1, Gemini-2.5-Flash, and Grok-4.1-fast-reasoning – across multiple prompting strategies including Chain-of-Thought (CoT) and Tree-of-Thought (ToT) 9 ; 12 . We also introduce a three-stage hint protocol that progressively reveals construction errors, enabling us to assess whether LLMs can self-correct when guided. Main Findings. Our results reveal a stark dissociation between knowledge and reasoning: all models achieve 100% accuracy on factual questions and 84–90% on seen construction tasks, but accuracy drops sharply on unseen problems (20.67–59.12% under direct prompting, representing 30–64 % point drops). Detailed error analysis shows systematic failure modes: incorrect simplification of Kleene star semantics, failure to preserve constraints under concatenation, and introduction of spurious states. Critically, these failures persist across all prompting strategies, and the hint protocol primarily corrects shallow errors while leaving globally inconsistent automata uncorrected. Contributions. This work makes the following contributions: (i) Novel benchmark: We introduce the first DFA construction benchmark with systematic seen/unseen splits, comprising 50 knowledge, 90 seen, and 180 unseen problems (60 hand-crafted, 120 via Arden’s theorem). (ii) Controlled memorization study: By evaluating structurally similar seen/unseen pairs, we provide the first evidence that LLM success on ToC tasks primarily reflects memorization rather than compositional reasoning. (iii) Comprehensive prompting evaluation: We evaluate CoT, ToT (with four construction methods: direct, minimization, derivative-based, Thompson’s algorithm), and a novel hint-based self-correction protocol. (iv) Systematic failure taxonomy: Through detailed analysis of 500+ incorrect DFAs, we identify six recurring failure modes (derivative normalization errors, constraint composition failures, etc.) that reveal fundamental limitations in symbolic state tracking. All datasets, prompts, evaluation code, and model outputs are released at https://anonymous.4open.science/r/dfa-llm-evaluation-B82D/ to support reproducibility and future research on formal reasoning in LLMs. 2 Seen Dataset and Task Formulation 2.1 Task Definition We evaluate LLMs on the task of constructing deterministic finite automata (DFAs) from formal language specifications. Given a target language L specified either as a regular expression (RE) or natural language description, the model must produce a DFA D=\langle\mathcal{Q},\Sigma,\delta,q_{0},F\rangle that recognizes exactly L . Here, \mathcal{Q} is a finite set of states, \Sigma is the input alphabet, \delta:\mathcal{Q}\times\Sigma\rightarrow\mathcal{Q} is the transition function, q_{0}\in\mathcal{Q} is the start state, and F\subseteq\mathcal{Q} is the set of accepting states 8 . A DFA D accepts string w=w_{1}w_{2}\cdots w_{n}\in\Sigma^{*} if there exists a sequence of states s_{0},s_{1},\ldots,s_{n} such that (i) s_{0}=q_{0} , (ii) s_{i}=\delta(s_{i-1},w_{i}) for all 1\leq i\leq n , and (iii) s_{n}\in F . We say D recognizes language L if L=\{w\in\Sigma^{*}\mid D\text{ accepts }w\} . A language is regular if there exists a DFA that recognizes it. Correct DFA construction requires models to: (1) parse and interpret formal language specifications, (2) identify the minimal state structure capturing all constraints, (3) design transitions ensuring acceptance of all and only valid strings, and (4) maintain global consistency across all states and symbols. Critically, there exist exponentially many invalid DFAs for any language, and small errors in state semantics or transition assignments can invalidate the entire construction. (a) Correct minimal DFA for L_{1} (b) Correct minimal DFA for L_{2} (c) Gemini-2.5 output for L_{2} Figure 1: (a): Minimum DFA for language L_{1} ; (b) & (c): Comparison of correct minimal DFA for unseen language L_{2} (see b) and representative incorrect output (see c). Notation: \bigcirc = state, \triangleright = start state, \circledcirc = accepting state. Transition q_{0}\xrightarrow{a}q_{1} indicates that on input a from state q_{0} , the DFA transitions to state q_{1} (Please zoom for better readability) . Problem Instances. Each problem specifies the target language in one of two formats: (a) Natural language: L_{1} = {Construct a DFA over \{a,b\} that accepts all strings in which the third-to-last symbol from the end must be ‘a’}. Here, if the problem format is given in natural language, it is not possible to design DFA using Lex, Flex 1 . (b) RE: L_{1}=(a+b)^{*}a(a+b)(a+b) . Both formats specify the same language (Figure 1 (a)). Models must output a complete DFA specification including states, transitions, start state, and accepting states. We focus on minimal

Read the complete text