A direct method for string to deterministic finite automaton conversion for fast text searching
G.J. Berlin · University of North Texas Digital Library (University of North Texas) · 1991
This paper describes a simple technique for generating a minimum state deterministic finite automation (DFA) directly from a restricted set of regular expressions. The resulting DFA is used for string searches that do not alter the target text and require only a single pass through the input. The technique is used for very fast, mixed or same case, single or multiple string searches. The technique is also capable of directly converting multiple strings with wild card character specifiers by constructing parallel DFAs. Construction of the automation is performed in a time proportional to the length of the regular expression. Algorithms are given for construction of the automatons and recognizers. Although the regular expression to DFA parser does not support all classes of regular expressions, it supports a sufficient subset to make it useful for the most commonly encountered text searching functions.