Determination and handling of subexpression overlaps in regular expression decompostions

A computer system for transforming a finite state automaton (FSA) of a regular expression, the computer system configured to:

• determine, by a processor of the computer system, a first subexpression R1 and a second subexpression R2 in the regular expression;
• calculate an overlap FSA, the overlap FSA configured to determine the existence of a partial overlap or a full overlap between the first subexpression R1 and the second subexpression R2;
• determine whether the overlap FSA has an accepting state;
• and
• in the event the overlap FSA is determined not to have an accepting state, determine that the transformation of the regular expression is safe, and construct a transformed FSA of the regular expression comprising a first FSA for the first subexpression R1 and a second FSA for the second subexpression R2.

A computer-implemented method for transforming a finite state automaton (FSA) of a regular expression, the method comprising:

• determining, by a computer, a first subexpression R1 and a second subexpression R2 in the regular expression;
• calculating an overlap FSA, the overlap FSA configured to determine the existence of a partial overlap or a full overlap between the first subexpression R1 and the second subexpression R2;
• determining whether the overlap FSA has an accepting state;
• and
• in the event the overlap FSA is determined not to have an accepting state, determining that the transformation of the regular expression is safe, and constructing a transformed FSA of the regular expression comprising a first FSA for the first subexpression R1 and a second FSA for the second subexpression R2.