✦ LIBER ✦
Translation of binary regular expressions into nondeterministic ε-free automata with O(n log n) transitions
✍ Scribed by Viliam Geffert
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 281 KB
- Volume
- 66
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
We show that every regular expression of size n over a fixed alphabet of s symbols can be converted into a nondeterministic e-free finite-state automaton with Oðsn log nÞ transitions (edges). In case of binary regular languages, this improves the previous known conversion from Oðnðlog nÞ 2 Þ transitions to Oðn log nÞ: For the general case with no bound on cardinality of the input alphabet, our conversion yields a better constant factor in the Oðnðlog nÞ 2 Þ term. The number of states is bounded by OðnÞ: