神经网络可精确模拟有限状态机，实现符号计算与深度学习的融合。
Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
- 将状态转移展开为网络层，用神经网络直接构建确定性有限自动机。
- 证明固定深度网络无法处理需要无限记忆的非正则语言。
- 提供可验证的构造性设计，适合研究神经符号系统的人参考。
我们建立了一个完整的理论与实证框架，证明前馈神经网络可作为通用有限状态机（N-FSM）。结果表明，有限深度的ReLU和阈值网络可通过将状态转移展开为逐层结构，精确模拟确定性有限自动机（DFA），并给出了所需深度、宽度及状态压缩的严格刻画。我们证明了DFA转移是线性可分的，二值阈值激活可实现指数级压缩，Myhill-Nerode等价类可嵌入连续潜在空间并保持可分性。同时，我们形式化了表达能力边界：固定深度前馈网络无法识别需无界记忆的非正则语言。不同于以往基于启发式或探测的研究，本工作提供构造性证明，并设计出可实证验证每项结论的显式DFA展开神经架构。研究成果连接深度学习、自动机理论与神经符号计算，为离散符号过程在连续神经系统中的实现提供了严谨蓝图。
原文摘要 · Abstract (English)
We present a complete theoretical and empirical framework establishing feedforward neural networks as universal finite-state machines (N-FSMs). Our results prove that finite-depth ReLU and threshold networks can exactly simulate deterministic finite automata (DFAs) by unrolling state transitions into depth-wise neural layers, with formal characterizations of required depth, width, and state compression. We demonstrate that DFA transitions are linearly separable, binary threshold activations allow exponential compression, and Myhill-Nerode equivalence classes can be embedded into continuous latent spaces while preserving separability. We also formalize the expressivity boundary: fixed-depth feedforward networks cannot recognize non-regular languages requiring unbounded memory. Unlike prior heuristic or probing-based studies, we provide constructive proofs and design explicit DFA-unrolled neural architectures that empirically validate every claim. Our results bridge deep learning, automata theory, and neural-symbolic computation, offering a rigorous blueprint for how discrete symbolic processes can be realized in continuous neural systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。