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:
- 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$.
- 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$.
- Run the table-filling algorithm to test the equivalence of $(q_D, q_M)$.
- 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?