Patent ID: 7240048

Claim:
A deterministic finite state automaton (FSA), responsive to an n-symbol alphabet, adapted to match, in parallel, m patterns each comprised of sequentially ordered symbols selected from said alphabet, the FSA comprising: an initial state adapted to store therein n nextState transitions, each transition being responsive to a respective one of said symbols in said alphabet; a plurality of states, each corresponding to one symbol contained at a given position in one or more of said m patterns, and being adapted to store therein n nextState transitions, each transition being responsive to a respective one of said symbols in said alphabet; wherein: said initial state has stored therein a plurality of transitions each to a first state responsive to a first symbol of one or more of said m patterns; each state which corresponds to position i in one or more of said m patterns having stored therein j transitions to the j next sequential states each responsive to a particular symbol at position i+l in one or more of said m patterns, such that each of said m patterns is associated with one unique sequential set of successive transitions from the initial state; if, after s sequential symbols in any one A of said m patterns, a sequence of no more than t sequential symbols corresponds to the first t symbols of a pattern B from amongst said m patterns, where t is at least one but less than the number of symbols in pattern B, then the (s+t) state of said unique sequential set associated with pattern A of successive transitions from the initial state also has stored therein a transition to the (t+1) state of said unique sequential set associated with pattern B of successive transitions from the initial state.