### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012) |

Editors | J. Holub, J. Zdarek |

Place of Publication | Prague |

Publisher | Czech Technical University in Prague |

Pages | 28-41 |

ISBN (Print) | 978-80-01-05095-8 |

Publication status | Published - 2012 |

### Fingerprint

### Cite this

*Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)*(pp. 28-41). Prague: Czech Technical University in Prague.

}

*Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012).*Czech Technical University in Prague, Prague, pp. 28-41.

**Failure deterministic finite automata.** / Kourie, D.G.; Watson, B.W.; Cleophas, L.G.W.A.; Venter, F.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Failure deterministic finite automata

AU - Kourie, D.G.

AU - Watson, B.W.

AU - Cleophas, L.G.W.A.

AU - Venter, F.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 978-80-01-05095-8

SP - 28

EP - 41

BT - Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)

A2 - Holub, J.

A2 - Zdarek, J.

PB - Czech Technical University in Prague

CY - Prague

ER -