Large Language Models Struggle With DFA Construction

Researchers introduce a benchmark testing large language models' ability to construct deterministic finite automata (DFAs) from regular-language descriptions, submitted Jan. 19, 2026. Models achieve perfect accuracy on factual items and 84–90% on seen constructions, but accuracy drops 30–64% on unseen, handcrafted and Arden's-theorem-generated problems; failures include constraint misinterpretation, Kleene-star errors, and global inconsistency, while a hint protocol only partially corrects shallow mistakes.