A study of connectionist approaches in DFA learning

Abstract

Deterministic finite-state automata (DFA) are used to recognise strings or words in a regular language. DFA learning is usually the task of learning the smallest DFA consistent with a given training set of strings that belong to and do not belong to a regular language. DFA learning is typically achieved through either state-merging or connectionist approaches, which are compared in this FYP. State-merging starts with a highly specific hypothesis DFA and iteratively merges it down to a smaller DFA consistent with the training data. Connectionist approaches involve using neural networks composed of interconnected neurons, such as recurrent neural networks (RNNs). RNNs process sequential data and have shown promising results in previous studies. The primary aim of this FYP is to evaluate the effectiveness of RNNs in learning DFAs and compare their performance with the state-of-the-art, non-backtracking state-merging algorithm EDSM. DFA learning is implemented using RNNs in Python, alongside a DFA learning toolkit, DfaGo, for state-merging implementations. In all cases, the results are evaluated using the same datasets, created according to the Abbadingo One DFA learning challenge protocol. The results of this FYP point towards two findings. For sparse datasets, it was noted that RNNs have the ability to retain a certain learning rate better than the state-merging algorithms. Additionally, it was shown that second-order RNNs have decisive effect on the model’s outcome in comparison to first-order RNNs, especially for larger size DFAs. Overall, this FYP highlights the importance of exploring different techniques for DFA learning and the potential of connectionist approaches in this field.