×

Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata. (English) Zbl 1014.68093

Summary: We prove that every regular expression of size \(n\) can be converted into an equivalent Nondeterministic \(\varepsilon\)-free Finite Automaton (NFA) with \(O(n\log n)^2)\) transitions in time \(O(n^2\log n)\). The best previously known conversions result in NFAs of worst-case size \(\Theta(n^2)\). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular expressions of size \(O(n)\) and show the number of transitions required in equivalent NFAs is \(\Omega(n\log n)\). This also proves there does not exist a linear-size conversion from regular expressions to NFAs.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Book, R.; Even, S.; Greibach, S.; Ott, G., Ambiguity in graphs and expressions, IEEE Trans. Comput., 20, 149-153 (1971) · Zbl 0222.94067
[2] Brüggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci., 120, 197-213 (1993) · Zbl 0811.68096
[3] Crochemore, M.; Hancart, C., Automata for matching patterns, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 2: Linear Modeling: Background and Application (1997), Springer-Verlag: Springer-Verlag Berlin), 399-462
[4] Chang, C.-H.; Paige, R., From regular expressions to DFA’s using compressed NFA’s, Theoret. Comput. Sci., 178, 1-36 (1997) · Zbl 0912.68105
[5] Ehrenfeucht, A.; Zeiger, P., Complexity measures for regular expressions, J. Comput. System Sci., 12, 134-146 (1976) · Zbl 0329.94024
[6] Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys, 16, 1-53 (1961) · Zbl 0104.35404
[7] Hagenah, C.; Muscholl, A., Computing \(ε\)-free NFA from regular expressions in \(O(n log^2(n))\) time, (Prim, L., MFCS ’98. MFCS ’98, Springer Lecture Notes in computer Science (1998), Springer-Verlag: Springer-Verlag Berlin), 277-285 · Zbl 0912.68113
[8] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading · Zbl 0196.01701
[9] Hromkovič, J.; Seibert, S.; Wilke, T., Translating regular expression into small \(ε\)-free nondeterministic automata, (Reischuk, R.; Morvan, M., STACS 97. STACS 97, Vol. 1200 of Lecture Notes in Computer Science (1997), Springer-Verlag: Springer-Verlag Berlin), 55-66 · Zbl 1498.68138
[10] McNaughton, R. F.; Yamada, H., Regular expressions and state graphs for automata, IRE Trans. Electron. Comput., 9, 39-47 (1960) · Zbl 0156.25501
[11] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Develop., 3, 114-125 (1959) · Zbl 0158.25404
[12] Sippu, S.; Soisalon-Soininen, E., Parsing Theory, Vol. I: Languages and Parsing. Parsing Theory, Vol. I: Languages and Parsing, Vol. 15 of EATCS Monographs on Theoretical Computer Science (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0651.68007
[13] Thompson, K., Regular expression search, Commun. ACM, 11, 419-422 (1968) · Zbl 0164.46205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.