Category:Finite automaton string search algorithm

From LiteratePrograms
Jump to: navigation, search
Error creating thumbnail: /bin/bash: rsvg: command not found
DFA for searching for the string "MOMMY". Each time the double-circled state is reached, a match has been found. All unspecified transitions return to the initial state in the upper left.

The finite automaton string search algorithm works by constructing a simple state machine associated with the string being searched for. As it consumes the string being searched, the current state indicates a set of possible positions in the string being searched for. It can be generalized to search for arbitrary regular expressions. For example, to the right is the state machine associated with the search word "MOMMY". The procedure is a special case of the powerset construction procedure used to transform a nondeterministic finite automaton (NFA) into a deterministic finite automaton, since it is easy to create an NFA that recognizes a particular substring.

hijacker
hijacker
hijacker
hijacker

Pages in category "Finite automaton string search algorithm"

The following 2 pages are in this category, out of 2 total.