CODEWITHSUNDEEP
regexregular-languagefinite-automataautomatadfa
Gabrer
Gabrer

Reputation: 475

Check if 2 minimum DFA are equivalent

I have 2 minimized DFA and i need to check if they are equivalent.

If they are equivalent, the problem is to find a efficient comparison of state regardless of different labels. In my case DFA are table, then i need to find the permutation that match the rows of first DFA with rows of second DFA.

I thought also about to have a Breadth-first search of DFA and create the minimum access string to a state and then compare the first list with the second list (this should be regardless of the particular input, for example: 001 and 110 could be interchangeable).

I'm interesting either to direct and inefficient algorithm and to more sophisticated algorithm.

Upvotes: 1

Views: 2376

Answers (3)

Zhiyang Chen
Zhiyang Chen

Reputation: 1

I remeber a minimum DFA is unique. So if you have 2 minimized DFA, I think you only need to check whether they're the same.

Upvotes: 0

Gabrer
Gabrer

Reputation: 475

I found these algorithms:

 - Symmetric difference
 - Table-filling algorithm
 - Faster Table-Filling algorithm O(n^2)
 - Hopcroft algorithm
 - Nearly Linear algorithm by Hopcroft and Karp

A complete reference is:

I accepted this my answere because the one of @abbaasi is too incomplete. I will accept any other answer with a significant contribution.

Upvotes: 0

Hassan Abbasi
Hassan Abbasi

Reputation: 272

The right approach is to construct another DFA with: L3=(L1-L2) U (L2-L1) And test whether L3 is empty or not. If L3 is empty then L1=L2, otherwise L1<>L2

Upvotes: 2

Related Questions