Patent ID: 7765183

Claim:
An apparatus for processing a hierarchical deterministic finite automata (DFA) produced from a plurality of regular expressions, the hierarchical DFA including a root DFA a plurality of leaf DFAs, the apparatus comprising: means for traversing the hierarchical DFA in response to a sequence of characters and for identifying matches to one or more of said regular expressions; wherein said means for traversing the hierarchical DFA includes means for traversing the root DFA and for activating said leaf DFAs in response to reaching or traversing corresponding one or more activation states or arcs within the root DFA; wherein each of said leaf DFAs includes a terminating state or arc; wherein said means for traversing the hierarchical DFA includes means for terminating the traversing of a particular one of said leaf DFAs in response to reaching or traversing a corresponding terminating state or arc in said particular one of said leaf DFAs; wherein at said termination state or arc of at least one of said leaf DFAs causes a corresponding said leaf DFA to become inactive without producing a match with the hierarchical DFA continuing to be processed by said means for traversing the hierarchical DFA.