Patent ID: 8793251

Claim:
In a system including a first automaton for finding a match between an input string and a regular expression and including a second automaton for extracting submatches corresponding to capturing groups in the regular expression, a method for creating input partitions for the first and second automata, the method comprising: grouping a plurality of first state transition entries of the first automaton into a first automaton input partition when all of the first state transition entries cause the first automaton to transition from a first current state to the same first next state; and grouping a plurality of selected states of the first automaton into a second automaton input partition when (1) all of the selected states cause the second automaton to transition from a second current state to the same second next state and (2) all of the selected states cause the second automaton to output a same tag value, wherein the tag value indicates a start and an end of a corresponding extracted submatch.