Positionally dependent pattern checking in character strings using deterministic finite automata

Abstract

A deterministic finite state machine organised for the detection of positionally significant matches of characters in a string of characters examines each character in turn to determine a exit transition for a current state of the machine to another state The machine responds to an examination of the string of characters by executing in response to a first character at the commencement of the string a transition from an initial state to another state. The machine has at least one state for every character position, includes a exit transition from each state for each character to another state; and possesses only forward exit transitions each from any of the states whereby the current state of the machine unambiguously represents a count of the number of characters from the commencement of the string. The machine may include at least one match state which indicates that all character matches in the string required by at least one respective rule have been detected. Some but not all the states in the multiplicity of states each have a single exit transition for any value of a respective character in the string. At least some of the states in the multiplicity of states each define an exit transition to a state indicating 'no match'. The machine may be disposed to cease its examination of the character string on attaining a 'no match'state.