DFA sequential matching of regular expression with divergent states

A method for use in identifying matches to a series of regular expressions, the series of regular expressions including a first regular expression followed by a second regular expression, the method comprising:

• creating, by a particular machine, a first deterministic finite automaton (DFA) for the first regular expression;
• creating, by the particular machine, a second DFA for the second regular expression;
• and
• merging, by the particular machine, the first DFA and the second DFA to create a merged DFA with a particular state within the merged DFA corresponding to both a starting state of the second DFA and to a final state of the first DFA, the merged DFA including a plurality of convergent states and a plurality of divergent states, the plurality of divergent states including one or more divergent states forming one or more traversable paths from the particular state to a particular final state of the second DFA;
• wherein a distinction between convergent and divergent states provides at least a mechanism for use in identifying whether or not a particular traversal of the merged DFA from the first time reaching the particular state to the particular final state should or should not correspond to a matching of the second regular expression;
• wherein the particular traversal reaching the particular final state results in a matching of the second regular expression if the particular traversal includes at least one convergent state, else the particular traversal reaching the particular final state does not result in a matching of the second regular expression.

One or more tangible computer-readable media containing computer-executable instructions for performing operations for use in identifying matches to a series of regular expressions, the series of regular expressions including a first regular expression followed by a second regular expression, said operations comprising:

• creating a first deterministic finite automaton (DFA) for the first regular expression;
• creating a second DFA for the second regular expression;
• and merging the first DFA and the second DFA to create a merged DFA with a particular state within the merged DFA corresponding to both a starting state of the second DFA and to a final state of the first DFA, the merged DFA including a plurality of convergent states and a plurality of divergent states, the plurality of divergent states including one or more divergent states forming one or more traversable paths from the particular state to a particular final state of the second DFA;
• wherein a distinction between convergent and divergent states provides at least a mechanism for use in identifying whether or not a particular traversal of the merged DFA from the first time reaching the particular state to the particular final state should or should not correspond to a matching of the second regular expression;
• wherein the particular traversal reaching the particular final state results in a matching of the second regular expression if the particular traversal includes at least one convergent state, else the particular traversal reaching the particular final state does not result in a matching of the second regular expression.

A method, performed by a particular machine for use in identifying matches to a series of regular expressions, the series of regular expressions including a first regular expression followed by a second regular expression, the method comprising:

• traversing, by the particular machine, a first deterministic finite automaton (DFA) corresponding to the first regular expression based on a series of characters for identifying a match between the first regular expression and the series of characters;
• traversing, by the particular machine, a second DFA corresponding to the second regular expression based on the series of characters for identifying one or more matches between the second regular expression and the series of characters;
• traversing, by the particular machine, a third DFA corresponding to a divergent portion of the second regular expression based on characters in the string of characters subsequent to the first-time match of the first regular expression for identifying a match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression;
• and
• wherein the matching of the second regular expression for identifying whether the series of regular expression is matched determined by the third DFA identifying the match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression or if the third DFA is no longer relevant for identifying the matching of the second regular expression, in response to the second DFA identifying a match between the second regular expression and the series of characters.

One or more tangible computer-readable media containing computer-executable instructions for performing operations for use in identifying matches to a series of regular expressions, the series of regular expressions including a first regular expression followed by a second regular expression, said operations comprising:

• traversing a first deterministic finite automaton (DFA) corresponding to the first regular expression based on a series of characters for identifying a match between the first regular expression and the series of characters;
• traversing a second DFA corresponding to the second regular expression based on the series of characters for identifying one or more matches between the second regular expression and the series of characters;
• traversing a third DFA corresponding to a divergent portion of the second regular expression based on characters in the string of characters subsequent to the first-time match of the first regular expression for identifying a match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression;
• and
• wherein the matching of the second regular expression for identifying whether the series of regular expression is matched determined by the third DFA identifying the match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression or if the third DFA is no longer relevant for identifying the matching of the second regular expression, in response to the second DFA identifying a match between the second regular expression and the series of characters.

An apparatus for use in identifying matches to a series of regular expressions, the series of regular expressions including a first regular expression followed by a second regular expression, the apparatus comprising:

• means for traversing a first deterministic finite automaton (DFA) corresponding to the first regular expression based on a series of characters for identifying a match between the first regular expression and the series of characters;
• means for traversing a second DFA corresponding to the second regular expression based on the series of characters for identifying one or more matches between the second regular expression and the series of characters;
• means for traversing a third DFA corresponding to a divergent portion of the second regular expression based on characters in the string of characters subsequent to the first-time match of the first regular expression for identifying a match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression;
• and
• wherein the matching of the second regular expression for identifying whether the series of regular expression is matched determined by the third DFA identifying the match between the second regular expression and the string of characters subsequent to the first-time match of the first regular expression or if the third DFA is no longer relevant for identifying the matching of the second regular expression, in response to the second DFA identifying a match between the second regular expression and the series of characters.