×

Conversion of regular expressions into realtime automata. (English) Zbl 1110.68063

Summary: We consider conversions of regular expressions into \(k\)-real-time finite state automata, i.e., automata in which the number of consecutive uses of \(\varepsilon\)-transitions, along any computation path, is bounded by a fixed constant \(k\). For 2-real-time automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only \(O(n)\) states, \(O(n\log n)\) \(\varepsilon\)-transitions, and \(O(n)\) alphabet-transitions. We also show how to easily transform these 2-real-time machines into 1-real-time automata, still with only \(O(n\log n)\) edges. These results contrast with the known lower bound \(\Omega(n(\log n)^2/\log\log n)\), holding for 0-real-time automata, i.e., for automata with no \(\varepsilon\)-transitions.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML Link

References:

[1] A. Ehrenfeucht and P. Zieger , Complexity measures for regular expressions . J. Comput. Syst. Sci. 12 ( 1976 ) 134 - 46 . Zbl 0329.94024 · Zbl 0329.94024
[2] V. Geffert , Translation of binary regular expressions into nondeterministic \(\varepsilon \)-free automata with \(O(n\log n)\) transitions . J. Comput. Syst. Sci. 67 ( 2003 ) 451 - 72 . Zbl 1055.68068 · Zbl 1055.68068
[3] S. Ginsburg , Algebraic and Automata-Theoretic Properties of Formal Languages . North-Holland ( 1975 ). MR 443446 | Zbl 0325.68002 · Zbl 0325.68002
[4] J.E. Hopcroft and J.D. Ullman , Introduction to Automata Theory , Languages, and Computation. Addison-Wesley ( 1979 ). MR 645539 | Zbl 0426.68001 · Zbl 0426.68001
[5] J. Hromkovič , S. Seibert and T. Wilke , Translating regular expressions into small \(\varepsilon \)-free nondeterministic automata , in Proc. Symp. Theoret. Aspects Comput. Sci. Lect. Notes Comput. Sci. 1200 ( 1997 ) 55 - 66 . Zbl 1014.68093 · Zbl 1014.68093
[6] J. Hromkovič , S. Seibert and T. Wilke , Translating regular expressions into small \(\varepsilon \)-free nondeterministic finite automata . J. Comput. Syst. Sci. 62 ( 2001 ) 565 - 88 . Zbl 1014.68093 · Zbl 1014.68093
[7] Yu. Lifshits , A lower bound on the size of \(\varepsilon \)-free NFA corresponding to a regular expression . Inform. Process. Lett. 85 ( 2003 ) 293 - 99 . · Zbl 1173.68555
[8] S. Sippu and E. Soisalon-Soininen , Parsing Theory , Vol. I: Languages and Parsing. EATCS Monographs in Theoret. Comput. Sci. 15 ( 1988 ). MR 960693 | Zbl 0651.68007 · Zbl 0651.68007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.