In this work, we introduce DeepDFA, a novel approach to identifying Deterministic Finite Automata (DFAs) from traces, harnessing a differentiable yet discrete model. Inspired by both the probabilistic relaxation of DFAs and Recurrent Neural Networks (RNNs), our model offers interpretability post-training, alongside reduced complexity and enhanced training efficiency compared to traditional RNNs. Moreover, by leveraging gradient-based optimization, our method surpasses combinatorial approaches in both scalability and noise resilience. Validation experiments conducted on target regular languages of varying size and complexity demonstrate that our approach is accurate, fast, and robust to noise in both the input symbols and the output labels of training data, integrating the strengths of both logical grammar induction and deep learning.

本文提出了DeepDFA，一种通过跟踪识别确定性有限自动机（DFA）的新方法，采用可微但离散的模型。该方法结合了DFA的概率松弛和递归神经网络（RNN）的启发，提供了训练后的可解释性，并在复杂度和训练效率上优于传统RNN。实验验证表明，该方法在各种规模和复杂度的目标正规语言上表现准确、快速且对噪声具有强韧性，充分结合了逻辑语法诱导和深度学习的优势。

深度DFA：通过神经概率松弛进行自动机学习