@inproceedings{mahmud-etal-2026-llms,
title = "Can {LLM}s Design Computational Machines? Pushdown Automaton Synthesis as a Test of Structured Computational Reasoning",
author = "Mahmud, Syed Mumtahin and
Lina, Nazira Jesmin and
Ridoy, Shahriyar Zaman and
Hasan, S. M. Muhtasimul and
Khan, Md Mosaddek",
editor = "Lee, Hung-Yi and
Dev, Sunipa and
Li, Jessy and
Elliott, Desmond",
booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EMNLP} 2026",
month = oct,
year = "2026",
address = "Budapest, Hungary",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.findings-emnlp.2058/",
pages = "43820--43845",
ISBN = "979-8-89176-462-0",
abstract = "Artificial intelligence has long been evaluated by its ability to perform computation and structured reasoning. While recent large language models (LLMs) demonstrate strong capabilities in language generation, code synthesis, and structured problem solving, it remains unclear whether they can construct formal computational mechanisms from high-level specifications. In this work, we investigate whether modern LLMs can synthesize pushdown automata (PDAs) from language descriptions expressed in natural language or mathematical form. Because PDA construction requires explicit reasoning about states, transitions, and stack-based memory, it provides a controlled test of structured symbolic reasoning. We introduce the task of pushdown automaton synthesis and develop an automated evaluation framework that verifies generated PDAs through structural buildability checks and execution-based validation. Using a benchmark of context-free languages with labeled test cases, we evaluate contemporary LLMs and analyze their ability to construct and execute formal computational machines. Our results show that current state-of-the-art LLMs struggle to reliably construct executable PDAs, indicating that synthesizing computational mechanisms requiring coordinated reasoning over state transitions and stack-based memory manipulation remains challenging for present-day models. All code and data are available at: \href{https://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.git}{https://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.git}"
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="mahmud-etal-2026-llms">
<titleInfo>
<title>Can LLMs Design Computational Machines? Pushdown Automaton Synthesis as a Test of Structured Computational Reasoning</title>
</titleInfo>
<name type="personal">
<namePart type="given">Syed</namePart>
<namePart type="given">Mumtahin</namePart>
<namePart type="family">Mahmud</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Nazira</namePart>
<namePart type="given">Jesmin</namePart>
<namePart type="family">Lina</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Shahriyar</namePart>
<namePart type="given">Zaman</namePart>
<namePart type="family">Ridoy</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">S</namePart>
<namePart type="given">M</namePart>
<namePart type="given">Muhtasimul</namePart>
<namePart type="family">Hasan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Md</namePart>
<namePart type="given">Mosaddek</namePart>
<namePart type="family">Khan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-10</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Findings of the Association for Computational Linguistics: EMNLP 2026</title>
</titleInfo>
<name type="personal">
<namePart type="given">Hung-Yi</namePart>
<namePart type="family">Lee</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Sunipa</namePart>
<namePart type="family">Dev</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jessy</namePart>
<namePart type="family">Li</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Desmond</namePart>
<namePart type="family">Elliott</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Budapest, Hungary</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-462-0</identifier>
</relatedItem>
<abstract>Artificial intelligence has long been evaluated by its ability to perform computation and structured reasoning. While recent large language models (LLMs) demonstrate strong capabilities in language generation, code synthesis, and structured problem solving, it remains unclear whether they can construct formal computational mechanisms from high-level specifications. In this work, we investigate whether modern LLMs can synthesize pushdown automata (PDAs) from language descriptions expressed in natural language or mathematical form. Because PDA construction requires explicit reasoning about states, transitions, and stack-based memory, it provides a controlled test of structured symbolic reasoning. We introduce the task of pushdown automaton synthesis and develop an automated evaluation framework that verifies generated PDAs through structural buildability checks and execution-based validation. Using a benchmark of context-free languages with labeled test cases, we evaluate contemporary LLMs and analyze their ability to construct and execute formal computational machines. Our results show that current state-of-the-art LLMs struggle to reliably construct executable PDAs, indicating that synthesizing computational mechanisms requiring coordinated reasoning over state transitions and stack-based memory manipulation remains challenging for present-day models. All code and data are available at: \hrefhttps://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.githttps://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.git</abstract>
<identifier type="citekey">mahmud-etal-2026-llms</identifier>
<location>
<url>https://aclanthology.org/2026.findings-emnlp.2058/</url>
</location>
<part>
<date>2026-10</date>
<extent unit="page">
<start>43820</start>
<end>43845</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Can LLMs Design Computational Machines? Pushdown Automaton Synthesis as a Test of Structured Computational Reasoning
%A Mahmud, Syed Mumtahin
%A Lina, Nazira Jesmin
%A Ridoy, Shahriyar Zaman
%A Hasan, S. M. Muhtasimul
%A Khan, Md Mosaddek
%Y Lee, Hung-Yi
%Y Dev, Sunipa
%Y Li, Jessy
%Y Elliott, Desmond
%S Findings of the Association for Computational Linguistics: EMNLP 2026
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-462-0
%F mahmud-etal-2026-llms
%X Artificial intelligence has long been evaluated by its ability to perform computation and structured reasoning. While recent large language models (LLMs) demonstrate strong capabilities in language generation, code synthesis, and structured problem solving, it remains unclear whether they can construct formal computational mechanisms from high-level specifications. In this work, we investigate whether modern LLMs can synthesize pushdown automata (PDAs) from language descriptions expressed in natural language or mathematical form. Because PDA construction requires explicit reasoning about states, transitions, and stack-based memory, it provides a controlled test of structured symbolic reasoning. We introduce the task of pushdown automaton synthesis and develop an automated evaluation framework that verifies generated PDAs through structural buildability checks and execution-based validation. Using a benchmark of context-free languages with labeled test cases, we evaluate contemporary LLMs and analyze their ability to construct and execute formal computational machines. Our results show that current state-of-the-art LLMs struggle to reliably construct executable PDAs, indicating that synthesizing computational mechanisms requiring coordinated reasoning over state transitions and stack-based memory manipulation remains challenging for present-day models. All code and data are available at: \hrefhttps://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.githttps://github.com/Dip-to/Pushdown-Automaton-Synthesis-Dataset.git
%U https://aclanthology.org/2026.findings-emnlp.2058/
%P 43820-43845
Markdown (Informal)
[Can LLMs Design Computational Machines? Pushdown Automaton Synthesis as a Test of Structured Computational Reasoning](https://aclanthology.org/2026.findings-emnlp.2058/) (Mahmud et al., Findings 2026)
ACL