PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q2(b)(i)

Theory of Computation · 1 marks

Open in the Padhaiko app

Topic: Closure Properties, Pumping Lemma & Decision Algorithms

Question

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:

  1. Convert both automata to DFAs and ensure their state sets are disjoint ().
  2. Construct the combined automaton .
  3. 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 .
  4. 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).

All past exam questions for Theory of Computation