0
$\begingroup$

The following question is taken from Sipser:

Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.

Here is the answer:

For any DFAs $A$ and $B$, $L(A) = L(B)$ if and only if $A$ and $B$ accept the same strings up to length $mn$, where $m$ and $n$ are the numbers of states of $A$ and $B$, respectively. Obviously, if $L(A) = L(B)$, $A$ and $B$ will accept the same strings. If $L(A) \neq L(B)$, we need to show that the languages differ on some string $s$ of length at most $mn.$ Let $t$ be a shortest string on which the languages differ. Let $l$ be the length of $t$. If $l \leq mn$ we are done. If not, consider the sequence of states $q_0,q_1,\dots,q_l$ that $A$ enters on input $t$, and the sequences of states $r_0,r_1,\dots,r_l$ that $B$ enters on input $t$. Because $A$ has $m$ states and $B$ has $n$ states, only $mn$ distinct pairs $(q,r)$ exist, where $q$ is a state of $A$ and $r$ is a state of $B$. By the pigeon hole principle, two pairs of states $(q_i,r_i)$ and $(q_j,r_j)$ must be identical. If we remove the portion of $t$ from $i$ to $j-1$, we obtain a shorter string on which $A$ and $B$ behave as they would on $t$. Hence we have found a shorter string on which the two languages differ, even though $t$ was supposed to be shortest. Hence $t$ must be no longer than $mn$.

Unfortunately, I do not understand the sequence of steps in the answer. Could anyone explain the answer for me in a simpler way?

$\endgroup$
  • 1
    $\begingroup$ There are several steps in the proof. Which of them do you have trouble with? $\endgroup$ – Yuval Filmus May 30 '18 at 11:31
  • 1
    $\begingroup$ Are you aware of the product construction? Can you show that if a non-empty language is accepted by a DFA having $n$ states, then it must contain a word whose length is smaller than $n$? If so, you can put the two together to answer the question. $\endgroup$ – Yuval Filmus May 30 '18 at 11:32
  • $\begingroup$ Can you transcribe the question and answer using MathJax? Images are hard to search, and hard to read for the visually impaired. $\endgroup$ – Yuval Filmus May 30 '18 at 11:32
  • $\begingroup$ @YuvalFilmus okay I will do as long as I have time >>>>> I am so sorry. $\endgroup$ – Intuition May 30 '18 at 11:33
  • $\begingroup$ @YuvalFilmus >>>> the sequence of the proof is not clear for me why it takes the above order ? $\endgroup$ – Intuition May 30 '18 at 11:35
3
$\begingroup$

Here is a slightly different proof, along similar lines.

Lemma 1. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. There is a DFA $C$ having $nm$ states such that $L(C) = [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)]$.

The proof uses the product construction (exercise).

Lemma 2. Let $C$ be a DFA having $p$ states. If $L(C) \neq \emptyset$ then $L(C)$ contains some word of length at most $p-1$.

Proof sketch. The language $L(C)$ is non-empty if some final state $q_f$ is reachable from the initial state $q_0$. The shortest path from $q_0$ to $q_f$ has length at most $p-1$, and this corresponds to a word of length at most $p-1$ in $L(C)$.

Theorem. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. Then $L(A) = L(B)$ iff for all words $w$ of length at most $nm-1$, either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.

Proof. If $L(A) = L(B)$ then the condition clearly holds. If $L(A) \neq L(B)$ then $\Delta := [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)] \neq \emptyset$. According to Lemma 1, there is a DFA having $nm$ states whose language is $\Delta \neq \emptyset$. According to Lemma 2 (with $p = nm$), there exists a word $w \in \Delta$ of length at most $nm-1$. This is a word for which it doesn't hold that either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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