Metadata only
Date
2005Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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. Show more
Publication status
publishedExternal links
Book title
Automata, Languages and ProgrammingJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Organisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics