Computing the follow automaton of an expression
Jean-Marc Champarnaud, Florent Nicart, Djelloul Ziadi
Small nondeterministic recognizers are very useful in practical applications based on regular expression
searching. The follow automaton, recently introduced by Ilie and Yu, is such a small recognizer, since it is a
quotient of the position automaton. The aim of this paper is to present an efficient computation of this quotient,
based on specific properties of the ZPC-structure of the expression. The motivation is twofold. Since this
structure is already a basic tool for computing the position automaton. Antimirov s automaton and Hromkovic s
automaton, the design of an algorithm for computing the follow automaton via this structure makes it easier to
compare all these small recognizers. Secondly such an algorithm provides a straightforward alternative to the
rather sophisticated handling of e-transitions used in the origianl algorithm.
Ninth International Conference on Implementation and Application of Automata, Kingston, Canada,
July 22-24, 2004.