Technical Report No. 33, July 1991 - Abstract

Anne Brüggemann-Klein:
Regular Expressions into Finite Automata

It is a well-established fact that each regular expression can be transformed into a non-deterministic finite automaton (NFA) with or without epsilon-transitions, and all authors seem to provide their own variant of the construction. Of these, Berry and Sethi have shown that the construction of an epsilon-free NFA due to to Glushkov is a natural representation of the regular expression, because it can be described in terms of the Brzozowksi derivatives of the expression. Moreover, the Glushkov construction also plays a significant role in the document processing area: The SGML standard, now widely adopted by publishing houses and government agencies for the syntactic specification of textual markup systems, uses deterministic regular expressions, i.e. expressions whose Glushkov automation is deterministic, as a description language for document types.

In this paper, we first show that the Glushkov automaton can be constructed in time quadratic in the size of the expression, and that this is worst case optimal. For deterministic expressions, our algorithm has been linear run time. This improves on the cubic time methods suggested in the literature. A major step of the algorithm consists in bringing the expression into what we call star normal form. This concept is also useful for characterizing the relationship between two types of unambiguity that have been studied in the literature. Namely, we show that, modulo a technical condition, an expression is strongly unambiguous if and only it is weakly unambiguous and in star normal form. This leads to our third result, a quadratic time decision algorithm for weak unambiguity, that improves on the bi-quadratic method introduced by Book et al.