NFAs With and Without ε-Transitions
METADATA ONLY
Loading...
Author / Producer
Date
2005
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The construction of an epsilon-free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may increase the number of transitions quadratically and its optimality with respect to the number of transitions is a long standing open problem. We show that there exist regular languages L. that can be recognized by NFAs with O (n log(2)n) transitions, but epsilon-free NFAs need Omega (n(2)) transitions to accept L-n. Hence the standard conversion cannot be improved significantly. However L-n requires an alphabet of size n, but we also construct regular languages K-n over {0, 1} with NFAs of size O (n log(2) n), whereas epsilon-free NFAs require size epsilon-free NFAs require size n center dot root(log2n) for every c < 1/2.
Permanent link
Publication status
published
External links
Book title
Automata, Languages and Programming
Journal / series
Volume
3580
Pages / Article No.
385 - 396
Publisher
Springer
Event
32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)