×

Computing \(\varepsilon\)-free NFA from regular expressions in \(O(n\log^2 (n))\) time. (English) Zbl 0971.68091

Summary: The standard procedure to transform a regular expression of size \(n\) to an \(\varepsilon\)-free nondeterministic finite automaton yields automata with \(O(n)\) states and \(O(n^2)\) transitions. For a long time this was supposed to be also the lower bound, but a result by [\((*)\) J. Hromkovič, S. Seibert and Th. Wilke, Lect. Notes Comput. Sci. 1450, 277-285 (1998)] showed how to build an \(\varepsilon\)-free NFA with only \(O(n\log^2(n))\) transitions. The current lower bound on the number of transitions is \(\Omega(n\log(n))\). A rough running time estimation for the Common Follow Sets (CFS) construction proposed by \((*)\) yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time \(O(n\log(n)+\text{size}\) of the output). On a CREW PRAM the CFS construction can be performed in time \(O(\log(n))\) using \(O(n+(\text{size of the output})/\log(n))\) processors. We also present a simpler proof of the lower bound on the number of transitions.

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68W01 General topics in the theory of algorithms
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML