A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression. (English) Zbl 1173.68555
Summary: Hromkovič et al. showed how to transform a regular expression of size \(n\) into an \(\varepsilon\)-free nondeterministic finite automaton (which defines the same language as the expression) with \(O(n)\) states and \(O(n\log^{2}(n))\) transitions. They also established a lower bound \(\Omega (n\log (n))\) on the number of transitions. We improve the lower bound to \(\Omega (\frac{n\log^2 n}{\log \log n})\).
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
formal languages; regular expressions; combinatorial problems; epsilon-free nondeterministic automataOnline Encyclopedia of Integer Sequences:
Minimal number of edges in e-free non-deterministic finite automata (NFA) for regular expression c_1?c_2?...c_n?.References:
| [1] | Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys. Russian Math. Surveys, Uspekhi Mat. Nauk. Russian Math. Surveys. Russian Math. Surveys, Uspekhi Mat. Nauk, Uspekhi Mat. Nauk, 17, 2(104), 270-62 (1962), Correction · Zbl 0104.35404 |
| [2] | Hagenah, Ch.; Muscholl, A., Computing \(ε\)-free NFA from regular expressions in \(O(n log^2(n))\) time, RAIRO Theoret. Inform. Appl., 34, 257-277 (2000) · Zbl 0971.68091 |
| [3] | Hromkovic̆, J.; Seibert, S.; Wilke, Th., Translating regular expressions into small \(ε\)-free nondeterministic finite automata, (Reischuk, R.; etal., Proc. of the 14th Annual Symposium on Theoretical aspects of Computer Science (STACS’97, Lübeck, Germany). Proc. of the 14th Annual Symposium on Theoretical aspects of Computer Science (STACS’97, Lübeck, Germany), Lecture Notes in Comput. Sci., 1200 (1997), Springer: Springer Berlin), 55-56 · Zbl 1498.68138 |
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.
