Regular expressions into finite automata (Q1314367)

It is well-known that the regular expressions can be translated into non- deterministic finite automata \((NFA)\) with or without \(\lambda\)- transitions. The standard method first translate a regular expression, in linear time, into an NFA with \(\lambda\)-transitions and then the \(\lambda\)-transitions are eliminated in quadratic time. There is another method, proposed by Glushkov and based on the fact that, if a word is denoted by an expression, it must be possible to spell out that word by tracing an appropriate ``path'' through the expression. It was shown that the Glushkov's method can be described in terms of Brzozowski derivatives and on the other hand this method plays an important role in document processing. In this paper the author shows that the Glushkov automaton associated to a regular expression can be constructed in quadratic time in the size of the expression, and in the case of deterministic expressions the construction can be done in linear time. The result is obtained first for regular expressions in star normal form (also introduced in this paper) and then it is translated to the general case. The paper is directed then on the unambiguity of the regular expressions and it is shown that the weak unambiguity can be tested in quadratic time improving the methods known until now. Finally, some interesting open problems are mentioned.