Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability
Sahil Rajesh Dhayalkar [email protected] · 2025
Read Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability 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-2509-10034.txt.
Introduction
Sahil Rajesh Dhayalkar's 2025 paper proves that a certain kind of neural network can copy a probabilistic finite automaton exactly, step for step. Such automata hop between states with set odds, the basic grammar of random sequences. His symbolic feedforward design stores the state distribution as a vector and each transition as a stochastic matrix, so one matrix multiplication advances the whole distribution without any recurrence in the network.
Subset construction and epsilon-closure, the classic tools for taming these automata, are rebuilt inside the layered computation, and equivalence with the automata is proved. The stronger claim is learnability: ordinary gradient training on labelled sequences recovers the true automaton's behaviour exactly. Symbolic rigour and gradient learning, often treated as rivals, meet here on paper.
Catalog record
| CREATOR | Sahil Rajesh Dhayalkar [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-10034
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability Sahil Rajesh Dhayalkar [email protected] Abstract We present a formal and constructive theory showing that probabilistic finite automata can be exactly simulated using symbolic feedforward neural networks. Our architecture represents state distributions as vectors and transitions as stochastic matrices, enabling probabilistic state propagation via matrix-vector products. This yields a parallel, interpretable, and differentiable simulation of probabilistic finite automata dynamics using soft updates without recurrence. We formally characterize probabilistic subset construction, finite ε \varepsilon -closure, and exact simulation via layered symbolic computation, and prove equivalence between probabilistic finite automata and specific classes of neural networks. We further show that these symbolic simulators are not only expressive but learnable: trained with standard gradient descent-based optimization on labeled sequence data, they recover the exact behavior of ground-truth probabilistic finite automata. This learnability, formalized in Proposition 5.1 , is the crux of this work. Our results unify probabilistic automata theory with classical neural architectures under a rigorous algebraic framework, bridging the gap between symbolic computation and deep learning. † † footnotetext: This paper has been submitted to IEEE Access and is currently under review. 1 Introduction Neural networks and automata represent two foundational paradigms in machine learning and theoretical computer science. Neural networks are continuous, differentiable, and data-driven; finite automata are discrete, symbolic, and rule-based. Bridging these paradigms has long been a goal of neural-symbolic learning Besold et al. 2017 ; d’Avila Garcez et al. 2019 , but most prior attempts have been empirical or heuristic, lacking rigorous guarantees of simulation or interpretability. This paper presents the first complete theoretical and empirical framework that constructs, simulates, and learns probabilistic finite automata (PFAs) using symbolic feedforward neural networks . We focus on PFAs—a powerful generalization of deterministic and nondeterministic automata—which model the stochastic evolution of state under probabilistic transitions Rabin 1963 ; Paz 1971 . Unlike deterministic finite automata (DFAs), where each input induces a unique state trajectory, PFAs compute the acceptance probability of a string by marginalizing over exponentially many paths, making them expressive yet computationally delicate. Despite their theoretical richness, PFAs remain largely unexplored in the context of modern neural networks. Existing works either ignore stochasticity or simulate automata using black-box recurrent models with limited interpretability Weiss et al. 2018 ; Hupkes et al. 2020 ; Hong et al. 2022 . This work closes that gap. We show that feedforward networks—without recurrence, memory, or sampling—can simulate PFAs exactly. Each layer in our architecture implements a stochastic state update using matrix-vector multiplication with symbolic transition matrices, followed by a softmax or sigmoid operation for normalization and classification. Our framework extends prior work on DFA Dhayalkar 2025a and NFA Dhayalkar 2025b simulation by unifying deterministic, nondeterministic, and probabilistic transitions under a single symbolic neural model. Formally, we define the simulation of PFAs by feedforward networks as the exact computation of the acceptance probability for any string via symbolic matrix composition. Proposition 4.7 and Theorem 4.10 prove a bidirectional equivalence: (1) every PFA can be simulated by a depth-unrolled feedforward network with shared stochastic parameters, and (2) every such symbolic network corresponds to a valid PFA. This allows us to replace automaton-based reasoning with static, interpretable network computation. Moreover, we define new symbolic mechanisms for probabilistic \varepsilon -closure (Lemma 4.6 ), probabilistic subset construction (Theorem 4.5 ), and belief state propagation (Proposition 4.1 ), all implemented as differentiable neural layers. Critically, our framework also supports learnability , which is the crux of our paper. Proposition 5.1 shows that symbolic feedforward networks not only simulate known PFAs but can be trained via gradient descent techniques to exactly recover unknown PFAs from data. We construct a learnable architecture where transition matrices are parameterized and normalized to remain stochastic. When trained with probabilistic acceptance labels, the network converges to exact simulators of the ground-truth PFA—achieving perfect accuracy and full semantic fidelity. This distinguishes our work from prior approaches that treat networks as black-box approximators without structure Butoi et al. 2025 , and offers a new paradigm: training symbolic automata directly within neural networks. Extensive experiments validate each theoretical result. We empirically confirm that our symbolic state vectors preserve probabilistic semantics, match ground-truth PFA dynamics exactly at each timestep, and simulate full acceptance behavior across randomly generated PFAs. Our learned models achieve exact recovery of the underlying automaton, demonstrating both expressivity and interpretability. The key contributions of this work are as follows. • We present the first constructive theory for simulating probabilistic finite automata (PFAs) with \varepsilon -transitions using symbolic feedforward networks. • We introduce exact formulations of probabilistic subset construction and finite \varepsilon -closure via matrix-vector dynamics, enabling differentiable automaton emulation. • We prove bidirectional equivalence between feedforward networks and PFAs (Theorem 4.10 ), establishing a formal link between symbolic state machines and neural models. • We demonstrate learnability (Proposition 5.1 ): symbolic neural networks can be trained from data to match ground-truth PFAs exactly, offering both statistical and structural fidelity. This is the central result of this paper. • We validate each theoretical claim through rigorous experiments across multiple random seeds, with full statistical reporting and semantic evaluations. This work advances the field of neural-symbolic computation by providing a unified, interpretable, and learnable framework for simulating probabilistic automata in neural networks. It lays the groundwork for deeper integration of formal language theory and deep learning, with applications in structured reasoning, interpretable sequence modeling, and symbolic control. 2 Related Work The study of neural networks as computational models has a long and rich history, spanning universal approximation theory Cybenko 1989 ; Hornik et al. 1989 , neural-symbolic integration Besold et al. 2017 ; d’Avila Garcez et al. 2019 , automata learning Weiss et al. 2018 ; Hupkes et al. 2020 ; Michalenko 2019 , and formal language recognition Hopcroft et al. 2006 ; Hays 2003 . This paper builds on this foundational work by developing a precise theoretical and empirical framework that characterizes how feedforward networks simulate probabilistic finite automata (PFAs), extending prior results from the deterministic setting Dhayalkar 2025a and non-deterministic setting Dhayalkar 2025b . 2.1 Neural-Symbolic Computation Early research in neural-symbolic computation sought to integrate symbolic reasoning with neural networks via hybrid architectures or recurrent logic units d’Avila Garcez et al. 2019 ; Besold et al. 2017 . These models demonstrated that certain forms of propositional logic could be encoded and manipulated within connectionist systems, yet often lacked rigorous formalism and focused primarily on logic inference rather than state-machine emulation. More recent efforts have introduced differentiable models of symbolic processes Graves 2017 , neural theorem proving Rocktäschel and Riedel 2017 , and neural architecture search over structured domains Łukasz Kaiser et al. 2017 . However, these methods have been largely heuristic or data-driven, often requiring supervision or pre-specification of symbolic structure. 2.2 Neural Networks as Automata Multiple works have explored whether and how neural networks implicitly implement automata when trained on regular or formal languages Weiss et al. 2018 ; Hupkes et al. 2020 ; Rabinovich et al. 2017 . These studies generally relied on probing internal representations of recurrent networks (RNNs, LSTMs, Transformers) to detect automaton-like behaviors such as state memorization or finite counting. Yet, such work remained empirical in nature, offering limited constructive insight into