Patent ID: 8688608

Claim:
A method for determining correctness of a transformation between a first finite state automaton (FSA) and a second FSA, wherein the first FSA comprises a representation of a regular expression, and the second FSA comprises a transformation of the first FSA, comprises: determining a third FSA, the third FSA comprising a cross product of the second FSA and a post-processor; determining whether the first FSA and the third FSA are equivalent, wherein determining whether the first FSA and the third FSA are equivalent comprises: converting the first FSA into first hardware description language code; converting the third FSA into second hardware description language code; converting the first hardware description language code into a first netlist; converting the second hardware description language code into a second netlist; building a composite netlist, the composite netlist comprising the first netlist and the second netlist; receiving a test data stream at an input of the composite netlist; and in the event an output of the composite netlist is asserted, determining that the first FSA is not equivalent to the third FSA; and in the event that the first FSA is determined not to be equivalent to the third FSA, determining that the transformation between the first FSA and the second FSA is not correct.