Computing ϵ-Free NFA from Regular Expressions in O(n log²(n)) Time

¹ Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany.
² LIAFA, Université Paris VII, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France; e-mail: muscholl@liafa.jussieu.fr
³ Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany. LIAFA, Université Paris VII, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France; e-mail: muscholl@liafa.jussieu.fr

Received: 31 August 1999
Accepted: 7 August 2000

Abstract

The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n²) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log²(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n) + size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions.