Equivalence between two machines

Question

What is the best or easiest way to determine equivalence between two automata?

Ie, if two finite state machines A and B are given, how to determine whether both languages ​​recognize the same language?

They are deterministic or both non-deterministic.

Answer 1

Two non-deterministic finite state machines (NFAs) are equivalent if they accept the same language.

To determine if they accept the same language, we look at the fact that each NFA has a minimum DFA, where the two states are not identical. Minimum DFA is also unique. Thus, given the two NFAs, if you find that their respective minimum DFAs are equivalent, then the two NFAs should also be equivalent.

For an in-depth study of this topic, I highly recommend that you read the Introduction to the Official Language and Automata .

Answer 2

Another, simpler approach is to complement and intersect automata. An automaton A equivalent to B if f L(A) contained in L(B) and vice versa if the intersection between the complement of L(B) and L(A) empty and vice versa.

Here is the algorithm for checking for the presence of L(A) in L(B) :

• Complementation: First define B by constructing a subset. Then make each receiving state rejective and accept each rejecting state. You get an automaton that recognizes the complement L(B) .
• Intersection: Build an automaton that recognizes a language that is the intersection of the complement of L(B) and L(A) . Ie, we construct an automaton for the intersection of the automaton from step 1 and A To intersect two automata U and V , you build an automaton with states U x V An automaton goes from state (u,v) to (u',v') with the letter A if there are transitions u --a--> u' to U and v --a--> v' to V The receiving states are the states (u,v) , where U receives in U and V receives in V
• After constructing the automaton in step 2, all that is needed is to check the void. Ie, there is a word that an automaton takes. This is the easiest part - to find the path in the machine from the initial state to the receiving state using the BFS algorithm.

If L(A) contained in L(B) , we need to run the same algorithm to check if L(B) is contained in L(A) .

Answer 3

I am simply paraphrasing @Guy's answer.

To compare the languages ​​adopted by both, we need to find out if L(A) is equal to L(B) or not.

So you need to find out if the value of L(A)-L(B) and L(B)-L(A) null or not. (Reasons1)

Part 1:

To find this, build NFA X from NFA A and NFA B, .

If X is empty, then L(A) = L(B) else L(A) != L(B) . (REASON2)

Part 2:

Now we need to figure out an effective way to prove or refute X is empty set . When will X be empty as DFA or NFA? Answer: X will be empty if there is no path leading from the start state to any of the final state of X. For this we can use BFS or DFS.

---

Reason1: If both values ​​have zero, then L(A) = L(B) .

Reason 2: We can prove that many regular languages ​​are closed with respect to intersection and union. In this way, we can efficiently create NFA X.

and for sets: