Home
Scholarly Works
Constructing NFAs by Optimal Use of Positions in...
Conference

Constructing NFAs by Optimal Use of Positions in Regular Expressions

Abstract

We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with ε-moves (εNFA) which are smaller than all the other εNFAs obtained by similar constructions. Their size is at most 3/2|α| + 5/2, where α is the regular expression. The second constructs NFAs. It uses ε-elimination in the εNFAs we just introduced and builds a quotient of the well-known position automaton. Our NFA is always smaller and faster to compute than the position automaton. It uses optimally the information from the positions of a regular expression.

Authors

Ilie L; Yu S

Series

Lecture Notes in Computer Science

Volume

2373

Pagination

pp. 279-288

Publisher

Springer Nature

Publication Date

January 1, 2002

DOI

10.1007/3-540-45452-7_23

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743
View published work (Non-McMaster Users)

Contact the Experts team