Hagenah, Christian; Muscholl, Anca Computing \(\varepsilon\)-free NFA from regular expressions in \(O(n\log^2 (n))\) time. (English) Zbl 0971.68091 Theor. Inform. Appl. 34, No. 4, 257-277 (2000). 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. Cited in 18 Documents 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 Keywords:nondeterministic finite automaton PDFBibTeX XMLCite \textit{C. Hagenah} and \textit{A. Muscholl}, Theor. Inform. Appl. 34, No. 4, 257--277 (2000; Zbl 0971.68091) Full Text: DOI EuDML