Equals() for DFA

[GoogleCodeExporter]

It's possible to check the equality of two DFA by using a recursive
algorithm. Two states are equal if all target states reachable from those
two states are also equal or there're none target states for both of those
two states.

So first check the input set of those two states, and then iterate through
all reachable target states, recursively call the check function on those
target states.

Two DFA is equivalent if their initial states are equivalent, or both of
them are empty DFA.

Original issue reported on code.google.com by lemontree.cool on 5 Sep 2008 at 3:11

[GoogleCodeExporter]

This is only useful in unit testing. Implement this as a helper function for 
unit
test should be sufficient. Anyway the algorithm doesn't deal with the "true" 
equality
of two DFA, only after "renaming" the states and to see whether those two DFA 
have
the same structure or not.

The "true" equality check should include performing the "minimization" operation
before the "renaming" operation. But since minimization is itself very hard to 
test
without the "true" equality check, we decide to leave this out.

Original comment by lemontree.cool on 6 Sep 2008 at 2:35

• Added labels: Priority-Low
• Removed labels: Priority-Medium

[GoogleCodeExporter]

Original comment by lemontree.cool on 13 Sep 2008 at 12:42

• Changed state: Fixed