An Assessment of Algorithms for Deriving Failure Deterministic Finite Automata

Madoda Nxumalo, Derrick G Kourie, Loek Cleophas, Bruce W Watson


Failure deterministic finite automata (FDFAs) represent regular languages more compactly than deterministic finite automata (DFAs). Four algorithms that convert arbitrary DFAs to language-equivalent FDFAs are empirically investigated. Three are concrete variants of a previously published abstract algorithm, the DFA-Homomorphic Algorithm (DHA). The fourth builds a maximal spanning tree from the DFA to derive what it calls a delayed input DFA. A first suite of test data consists of DFAs that recognise randomised sets of finite length keywords. Since the classical Aho-Corasick algorithm builds an optimal FDFA from such a set (and only from such a set), it provides benchmark FDFAs against which the performance of the general algorithms can be compared. A second suite of test data consists of random DFAs generated by a specially designed algorithm that also builds language-equivalent FDFAs, some of which may have non-divergent cycles. These random FDFAs provide (not necessarily tight) lower bounds for assessing the effectiveness of the four general FDFA generating algorithms.


Failure deterministic finite automata; random automata

Full Text:



Copyright (c) 2017 Madoda Nxumalo, Derrick G. Kourie, Loek Cleophas, Bruce W. Watson

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.