A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks

Sahil Rajesh Dhayalkar [email protected] · 2025

Read A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks by Sahil Rajesh Dhayalkar [email protected] (2025) 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-2505-24110.txt.

Introduction

Dhayalkar builds choice machines as unrolled feed nets with shared weights in this twenty twenty-five paper. Such machines read strings and branch on chance picks as they go. Past net takes used loop forms or dug the machine out post-drill.

Inside, states ride as bit strings and moves as sparse grid shifts in his build. Blank moves fold in as shared snap steps stacked by depth in the net. Proof shows each tongue such a machine takes fits one such net. Weight count stays fixed no count how long the string runs. Drill tests then teach fresh nets the same acts with near-full match.

Catalog record

CREATORSahil Rajesh Dhayalkar [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-24110

Browse the full library · About the Tower of Babel

Full text

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

A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks Sahil Rajesh Dhayalkar [email protected] Abstract We present a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs), i.e., acyclic unrolled computations with shared parameters that are functionally equivalent to unrolled recurrent or state-space models. Unlike prior approaches that rely on explicit recurrent architectures or post hoc extraction methods, our formulation symbolically encodes automaton states as binary vectors, transitions as sparse matrix transformations, and nondeterministic branching—including ε \varepsilon -closures—as compositions of shared thresholded updates. We prove that every regular language can be recognized exactly by such a shared-parameter unrolled feedforward network, with parameter count independent of input length. Our construction yields a constructive equivalence between NFAs and neural networks and demonstrates empirical learnability : these networks can be trained via gradient descent on supervised acceptance data to recover the target automaton behavior. This learnability, formalized in Proposition 5.1 , is the crux of this work. Extensive experiments validate the theoretical results, achieving perfect or near-perfect agreement on acceptance, state propagation, and closure dynamics. This work clarifies the correspondence between automata theory and modern neural architectures, showing that unrolled feedforward networks can perform precise, interpretable, and trainable symbolic computation. 1 Introduction The relationship between symbolic computation and neural networks has long fascinated both the theoretical computer science and machine learning communities. Finite automata Rabin and Scott (1959) ; Hopcroft et al. (2006) ; Sipser (1996) are among the most fundamental models of computation, capturing the essence of regular languages, while modern neural architectures LeCun et al. (2015) ; Goodfellow et al. (2016) ; Nair and Hinton (2010) ; Glorot et al. (2011) ; Lecun et al. (1998) ; Hochreiter and Schmidhuber (1997) ; Vaswani et al. (2017) are the cornerstone of deep learning systems. Despite their seemingly disparate origins, a growing body of research has sought to reconcile these paradigms by simulating automata within neural frameworks Giles et al. (1992) ; Weiss et al. (2018) ; Graves et al. (2014) . Early attempts primarily employed recurrent networks (RNNs) to approximate deterministic finite automata (DFAs), leveraging their sequential dynamics to process string inputs Giles et al. (1991) ; Korsky and Berwick (2019) . However, these approaches often required complex training, lacked interpretability, and provided no symbolic guarantees. More recent work has explored extracting automata from trained networks using queries and counterexamples Weiss et al. (2018) , or designing architectures with embedded stack or memory structures DuSell and Chiang (2022) ; Reed and de Freitas (2016) , but symbolic fidelity remained elusive. In this paper, we introduce a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs) —acyclic unrolled computation graphs with shared transition parameters. Functionally, these networks are equivalent to unrolled recurrent or state-space models (RNNs/SSMs) but expressed in a purely feedforward, static form. Our formulation symbolically encodes NFA states as binary vectors, transitions as sparse symbolic matrices, and nondeterministic branching—including \varepsilon -closures—as thresholded matrix compositions over shared transition matrices. We prove that every regular language accepted by an n -state NFA can be exactly simulated by such a shared-parameter unrolled feedforward network, with parameter count independent of input length. Our contribution lies in providing a constructive, exact, and interpretable simulation within a unified feedforward formalism. This work builds upon and clarifies prior efforts in neural–symbolic systems Bhattamishra et al. (2020) ; Merrill et al. (2020) ; Ergen and Grillo (2024) ; Graves et al. (2014) , offering a precise correspondence between finite automata transitions and thresholded neural updates. The key contributions of this work are as follows. 1. We provide a constructive and exact simulation of nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs) , encoding states as binary vectors and transitions as sparse symbolic matrices. 2. We establish a formal equivalence between TS-FFNs and NFAs by proving that every regular language can be recognized by such a network. The model uses \mathcal{O}(kn^{2}) parameters, independent of input length, enabling scalable simulation of arbitrarily long strings. 3. We show that \varepsilon -closure can be computed via iterative matrix-based thresholded updates, converging in at most n steps. 4. We demonstrate empirical learnability : TS-FFNs are learnable via gradient descent, achieving high accuracy in replicating NFA acceptance behavior using standard training on labeled data. This is the central result of this work. 5. We validate all theoretical results across multiple NFA configurations, showing perfect or near-perfect agreement on state propagation, acceptance, and symbolic equivalence. Together, these results provide a formal bridge between classical automata theory and deep learning. The paper is structured around definitions, theorems, lemmas, and corollaries, following the style of prior theoretical works Zhang et al. (2015) ; Hanin and Sellke (2018) ; Neyshabur et al. (2015) ; Dhayalkar (2025c) ; Dhayalkar (2025b) ; Dhayalkar (2025a) ; Stogin et al. (2024) . 2 Related Work This work builds on prior research at the intersection of automata theory, neural networks, and symbolic computation, and clarifies the position of our framework relative to existing efforts. Automata Simulation by Neural Networks: The idea of using neural networks to model automata has received significant attention. Early work explored the approximation of regular languages using recurrent networks (RNNs) Giles et al. (1992) , including techniques for training second-order networks to accept deterministic finite automata (DFAs) Giles et al. (1991) . More recent work has focused on extracting symbolic automata from trained RNNs using queries and counterexamples Weiss et al. (2018) or differentiable memory models such as Neural Turing Machines Graves et al. (2014) . These models typically rely on explicitly recurrent or sequential architectures with opaque internal representations. In contrast, our formulation expresses the same computational process within an acyclic, time-shared, depth-unrolled feedforward network (TS-FFN) that is functionally equivalent to an unrolled RNN/SSM, but expressed as a purely feedforward symbolic construction. Symbolic Interpretability of Neural Models: Efforts to interpret neural networks symbolically have grown with the popularity of neural–symbolic learning. Notable examples include differentiable pushdown automata DuSell and Chiang (2022) , differentiable interpreters Reed and de Freitas (2016) , and formal grammars embedded into transformer and RNN architectures Bhattamishra et al. (2020) ; Merrill et al. (2020) . These approaches aim to bridge symbolic logic and differentiable computation but often involve approximate, heuristic, or memory-augmented mechanisms. Our work provides an exact, constructive simulation of NFAs using shared-parameter unrolled feedforward layers, without additional memory modules or recurrent loops, while remaining equivalent in function to unrolled recurrent computation. Feedforward Networks and Formal Language Theory: The theoretical properties of neural networks with thresholded linear operations have been explored in the context of expressivity and piecewise linearity Nair and Hinton (2010) ; Goodfellow et al. (2016) . Recent studies have examined how such architectures can represent formal structures Dhayalkar (2025b) ; Ergen and Grillo (2024) . However, prior work has not provided a constructive, exact characterization of regular languages via shared-parameter feedforward networks. In this paper, we show that every NFA (and thus every regular language) can be encoded within a TS-FFN, where subset construction, \varepsilon -closures, and acceptance dynamics arise as exact compositions of symbolic matrix updates and thresholding operations. Learning Formal Languages with Neural Networks: Supervised learning of regular languages using neural networks

Read the complete text