Prague Stringology Conference 2012
Derrick G. Kourie, Bruce W. Watson, Loek Cleophas and Fritz Venter
Failure Deterministic Finite Automata
| Abstract: |
| Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA's transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA's algorithm for recognising language elements yields a corresponding algorithm for an FDFA. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |