Characterization of Glushkov automata
Glushkov's algorithm computes a nondeterministic finite automaton without epsilon-transitions and with n + 1 states from a regular expression having n occurrences of letters. The aim of this paper is to give a set of necessary and sufficient conditions characterizing this automaton. Our characterization theorem is formulated in terms of directed graphs. Moreover these conditions allow us to produce an algorithm of conversion of a Glushkov automaton into a regular expression of small size. (C) 2000 Elsevier Science B.V. All rights reserved.
regular expression glushkov automaton automata theory graphs theory