In 1964, J.A. Brzozowski introduced the notion of the derivatives of a regular expression [1]: where u is a word over the alphabet of a regular expression E, the derivative of E with respect to u is a regular expression for the set of words z, such that uz is a member of E. The finite set of derivatives can be the states of a deterministic finite automaton for E. In 1986, G. Berry and R. Sethi offered an alternative development of Brzozowski’s ideas [2].

Recent work by Champarnaud and Ziadi continues in this line. This paper includes adequate technical coverage of the ideas of Berry and Sethi, and develops new methods of converting regular expressions to finite automata.

This paper makes use of the linearization of a regular expression, namely, the rewriting of the expression so that no two positions are occupied by the same letter (for example, a linearization of a(a + b)*ba is a1(a2 + b3)*b4a5). Many problems concerning a given regular expression can be dealt with by first considering its linearization, since the derivative of the original expression is a homomorphic image of the derivative of the linearization.

Another concept is that of the partial derivative [3]. For example, the partial derivatives, with respect to e of the expression eb(c + db*), are bc and bdb* (the derivative itself is b(c + db*) ). The paper culminates with a discussion of the nondeterministic equation automaton for a language, whose states are the partial derivatives of a regular expression for the language, and where there is a transition from one state to another labeled b if the expression of the second state is a partial derivative, with respect to b of the expression of the first state. The paper presents an algorithm to construct an equation automaton from a given regular expression E. The time and space complexity of an improved version of this algorithm is O(|E|^2).