Past exam question: 2081 Chaitra (Regular), Q2(b)(i)
Open in the Padhaiko appQuestion
Write down the procedure to check the equivalence of two automata.
Solution
Procedure to Check Equivalence of Two Finite Automata: Two finite automata and are equivalent () if and only if they accept the exact same language: .
The standard decision procedure uses the State Equivalence / Table-Filling Algorithm on the Union Machine:
- Convert both automata to DFAs and ensure their state sets are disjoint ().
- Construct the combined automaton .
- Apply the table-filling algorithm to find all pairs of equivalent states in :
- Mark any pair where one state is in and the other is not.
- Iteratively mark pair if is already marked for some .
- Check the start state pair :
- If is unmarked, then .
- If is marked, then (the distinguishing string provides a counterexample).
(Alternative Symmetric Difference Method: Construct DFA for . iff , tested via BFS reachability of final states).
Answer:
To check if DFAs and are equivalent, construct the combined transition table over and run the table-filling algorithm. is equivalent to if and only if their initial states remain unmarked (indistinguishable).