3
$\begingroup$

In "Introduction to Automata Theory, Languages, and Computation" (John Hopcroft, Rajeev Motwani, Jeffrey Ullman), section 4.4.2 discussed an approach to test the equivalence of regular languages, i.e., given the representations of two regular languages $L$ and $M$, we want to know if $L = M$. The method in the section is as outlined:

  1. Convert the representations (e.g., DFA/NFA/$\epsilon$-NFA/regular expressions) of $L$ and $M$ to the respective DFA representations $D_L = (Q_D, \Sigma, \delta_D, q_D, F_D)$ and $D_M = (Q_M, \Sigma, \delta_M, q_M, F_M)$ where:
    • $Q_i$ is the set of states in the DFA, $\delta_i: Q_i \times \Sigma \rightarrow Q_i$ is the transition function, $q_i$ is the starting state and $F_i$ is the set of accepting states.
    • WLOG, by renaming if necessary, further assume that $Q_D \cap Q_M = \emptyset$.
  2. Construct a new DFA $D = (Q_D \cup Q_M, \Sigma, \delta_D \cup \delta_M, q, F_D \cup F_M)$ where the starting state $q$ is said to be irrelevant, and can be any state in $Q_D \cup Q_M$.
  3. Run the table-filling algorithm to test the equivalence of $(q_D, q_M)$.
  4. If $q_D$ and $q_M$ are equivalent, then $L = M$ since any string $w \in \Sigma^*$ is in $L$ iff it is in $M$. Otherwise, we say that $L \neq M$.

In the method, I am comfortable with steps 1, 3, 4, but particular confused about why the construction in step 2 works:

  • How do we interpret this new DFA $D$, given that $D$ is essentially made up of two disjoint pieces of DFA?
  • If we choose a new start state in $D_L$, then this start state can never reach states in $D_M$ (since $Q_D \cap Q_M = \emptyset$). How do we then discuss about the equivalence of states in the new DFA?
$\endgroup$

1 Answer 1

1
$\begingroup$

Two states are equivalent, if starting from these states we obtain the same language. There is no requirement that these states are actually reachable from the initial state, or that they are in the same component of the automaton.

Also testing equivalence of two states does not involve the initial state: we pretend those states are the initial states when comparing them. Hence the algorithm gives the right result despite your two objections.

$\endgroup$
2
  • $\begingroup$ there is a DFA reduction algorithm that defines when 2 states are equivalent(thus can be combined into 1 and reduce number of states by 1) is this somehow connected to that? $\endgroup$
    – math boy
    Commented Sep 19 at 9:08
  • 1
    $\begingroup$ @mathboy Yes, I believe the equivalence of states that is used here is the same that underlies minimization of DFA. $\endgroup$ Commented Sep 19 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.