Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-27T09:32:29.338Z Has data issue: false hasContentIssue false
  • English
  • Français

Conversion of regular expressionsinto realtime automata

Published online by Cambridge University Press:  08 November 2006

Viliam Geffert  and
L'ubomíra Ištoňová
Viliam Geffert
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04001 Košice, Slovakia; [email protected]; [email protected]
L'ubomíra Ištoňová
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04001 Košice, Slovakia; [email protected]; [email protected]
Get access

Abstract

We consider conversions of regular expressions into k-realtimefinite state automata, i.e., automata in which the number ofconsecutive uses of ε-transitions, along any computation path,is bounded by a fixed constant k. For 2-realtime automata,i.e., for automata that cannot change the state, without readingan input symbol, more than two times in a row, we show that theconversion of a regular expression into such an automaton producesonly O(n) states, O(nlogn) ε-transitions, and O(n)alphabet-transitions. We also show how to easily transform these2-realtime machines into 1-realtime automata, still with onlyO(nlogn) edges. These results contrast with the known lowerbound Ω(n(logn)2 / loglogn), holding for 0-realtimeautomata, i.e., for automata with no ε-transitions.

Keywords

Descriptional complexityfinite-state automataregularexpressions.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 4 , October 2006 , pp. 611 - 629
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ehrenfeucht, A. and Zieger, P., Complexity measures for regular expressions. J. Comput. Syst. Sci. 12 (1976) 134–46. CrossRef
Geffert, V., Translation of binary regular expressions into nondeterministic ε-free automata with O(nlogn) transitions. J. Comput. Syst. Sci. 67 (2003) 451–72. CrossRef
S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975).
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979).
J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic automata, in Proc. Symp. Theoret. Aspects Comput. Sci. Lect. Notes Comput. Sci. 1200 (1997) 55–66.
Hromkovič, J., Seibert, S. and Wilke, T., Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. Syst. Sci. 62 (2001) 565–88. CrossRef
Yu. Lifshits, A lower bound on the size of ε-free NFA corresponding to a regular expression. Inform. Process. Lett. 85 (2003) 293–99. CrossRef
S. Sippu and E. Soisalon-Soininen, Parsing Theory, Vol. I: Languages and Parsing. EATCS Monographs in Theoret. Comput. Sci. 15 (1988).