Conference
Follow automata
Abstract
We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with ε-transitions (εNFA) which are smaller than all the other εNFAs obtained by similar constructions. Their size is at most 32|α|+52, where α is the regular expression. This is very close to optimal since we prove also the lower bound 43|α|+52. The second constructs NFAs. It uses ε-elimination in the …
Authors
Ilie L; Yu S
Volume
186
Pagination
pp. 140-162
Publisher
Elsevier
Publication Date
October 2003
DOI
10.1016/s0890-5401(03)00090-7
Conference proceedings
Information and Computation
Issue
1
ISSN
0890-5401