Patent ID: 8620968

Claim:
A computer program product comprising a non-transitory computer readable storage medium containing computer code that, when executed by a computer, implements a method for transforming a finite state automaton (FSA) of a regular expression, wherein the method comprises: determining a first subexpression R 1 and a second subexpression R 2 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 R 1 and the second subexpression R 2 ; 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 R 1 and a second FSA for the second subexpression R 2 .