# Conversion of regular expressions into realtime automata

Viliam Geffert; L'ubomíra Ištoňová

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 4, page 611-629
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGeffert, Viliam, and Ištoňová, L'ubomíra. "Conversion of regular expressions into realtime automata." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 611-629. <http://eudml.org/doc/249737>.

@article{Geffert2006,

abstract = {
We consider conversions of regular expressions into k-realtime
finite state automata, i.e., automata in which the number of
consecutive 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 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(nlogn) ε-transitions, and O(n)
alphabet-transitions. We also show how to easily transform these
2-realtime machines into 1-realtime automata, still with only
O(nlogn) edges. These results contrast with the known lower
bound Ω(n(logn)2 / loglogn), holding for 0-realtime
automata, i.e., for automata with no ε-transitions.
},

author = {Geffert, Viliam, Ištoňová, L'ubomíra},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Descriptional complexity; finite-state automata; regular
expressions.; descriptional complexity; regular expressions},

language = {eng},

month = {11},

number = {4},

pages = {611-629},

publisher = {EDP Sciences},

title = {Conversion of regular expressions into realtime automata},

url = {http://eudml.org/doc/249737},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Geffert, Viliam

AU - Ištoňová, L'ubomíra

TI - Conversion of regular expressions into realtime automata

JO - RAIRO - Theoretical Informatics and Applications

DA - 2006/11//

PB - EDP Sciences

VL - 40

IS - 4

SP - 611

EP - 629

AB -
We consider conversions of regular expressions into k-realtime
finite state automata, i.e., automata in which the number of
consecutive 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 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(nlogn) ε-transitions, and O(n)
alphabet-transitions. We also show how to easily transform these
2-realtime machines into 1-realtime automata, still with only
O(nlogn) edges. These results contrast with the known lower
bound Ω(n(logn)2 / loglogn), holding for 0-realtime
automata, i.e., for automata with no ε-transitions.

LA - eng

KW - Descriptional complexity; finite-state automata; regular
expressions.; descriptional complexity; regular expressions

UR - http://eudml.org/doc/249737

ER -

## References

top- A. Ehrenfeucht and P. Zieger, Complexity measures for regular expressions. J. Comput. Syst. Sci.12 (1976) 134–46. Zbl0329.94024
- V. Geffert, Translation of binary regular expressions into nondeterministic ε-free automata with O(nlogn) transitions. J. Comput. Syst. Sci.67 (2003) 451–72. Zbl1055.68068
- S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975). Zbl0325.68002
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). Zbl0426.68001
- 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. Zbl1014.68093
- J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. Syst. Sci.62 (2001) 565–88. Zbl1014.68093
- Yu. Lifshits, A lower bound on the size of ε-free NFA corresponding to a regular expression. Inform. Process. Lett.85 (2003) 293–99. Zbl1173.68555
- S. Sippu and E. Soisalon-Soininen, Parsing Theory, Vol. I: Languages and Parsing. EATCS Monographs in Theoret. Comput. Sci.15 (1988). Zbl0651.68007

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.