Simulation of nondeterministic finite automata in pattern matching.

We present various nondeterministic finite automata (NFAs) for the approximate string and sequence matching. NFAs are usually easy to construct but their equivalent deterministic finite automata (DFAs) can have up to 2Q states, where Q is a number of states of considered NFA. This is only a theoretical upper bound, which is reached in rare cases in pattern matching. We also discuss sizes of equivalent DFAs for the approximate string and sequence matching NFAs. In the case the equivalent DFA cannot be used because of its enormous space requirements or the construction of the DFA takes to much time with respect to the length of input text, one can use a method that simulates a run of NFA.Available from STL Prague, CZ / NTK - National Technical LibrarySIGLECZCzech Republi