5
$\begingroup$

Given the language

$EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$

Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings upto a certain size. Calculate a size that works.

(This is from Sipser chapter 4)

I make a directed graph as usual but if two transitions $\delta(q_1, c_1) = q_2$ and $\delta(q_1, c_2) = q_2$ then the graph I am making will just have one edge for these two characters. My idea is to walk the directed graph in a way so that every transition is traversed, but when I walk over an edge forming a cycle, I would need to traverse the edges I have previously walked through in the cycle once again. Do this for both the DFAs and choose the greater number of edges traversed. Then enumerate through all the strings of this length (from the given alphabet) and the two DFAs are equal only if they accept and reject on the same strings.

I could probably write some pseudocode, but I'm not sure if this is the correct way to approach the problem even.

$\endgroup$
7
$\begingroup$

It can be tested that way, provided we may use the number of states of both automata $A$ and $B$ to compute the bound.

Note that if a finite automaton $C$ has $n$ states then any state in $C$ is reachable by a string of at most $n-1$ letters, or that state is not reachable at all. Assume I want to check whether $L(C)=\Sigma^*$. If $C$ is deterministic then all reachable states must be accepting. This can be tested by checking that all strings up to length $n-1$ are in the language.

The check $L(A)=L(B)$ can be analyzed similarly by considering the product automaton, i.e., the automaton that simulates $A$ and $B$ in parallel.

The product construction needs a little twist. Rather than accepting if both automata accept (computing the intersection) you need to see whether both automata make the same yes/no decision. Thus accept when both components are accepting or when both components are not accepting. Thus the language is $(L(A)\cap L(B))\cup (L(A)^c\cap L(B)^c)$. If that language is $\Sigma^*$ then both automata are equivalent.

$\endgroup$
  • $\begingroup$ (Just confirming if I understand correctly) I will run DFAs $A$ and $B$ and the DFA for $L(A) \cap L(B)$, the latter having $n$ states, on all strings upto length $n-1$ and accept only if for each string the results are the same for each DFA, right? $\endgroup$ – slnsoumik Oct 11 '15 at 23:28
  • $\begingroup$ In other words, you construct a FA that accepts the symmetric difference of $L(A)$ and $L(B)$ and then test that for emptiness, which you've already indicated can be done by testing only the "short" strings. Nice work. $\endgroup$ – Rick Decker Oct 12 '15 at 17:12
  • $\begingroup$ To see if I understand, we want to check if $(L(A) \cap L(B)) \cup (L(A)^c \cap L(B)^c) = \Sigma^*$. Assuming $L(A)$ has $m$ states and $L(B)$ has $n$ states, then the product construction has $mn$ states. Therefore we must test all strings up to length $mn - 1$. Assuming we have $k$ letters in our alphabet, we must then test $k^{mn-1}$ strings to determine if $L(A) = L(B)$. Did I understand correctly? $\endgroup$ – David Apr 24 at 2:54
1
$\begingroup$

By the (proof of the) pumping lemma, you'll need to check only strings of length up to the number of states of the DFA, probably the larger one. Would need to think it through, but I'm intrinsecally lazy.

$\endgroup$
  • 1
    $\begingroup$ Nope. The two automata do not necessarily pump/repeat at the same moment. That is why you want to construct a product automaton. Number of states is then the product of the respective states, not the maximum. $\endgroup$ – Hendrik Jan Oct 12 '15 at 15:41
-2
$\begingroup$

This seems an unusual method of attempting to determine equivalence of the languages of two DFAs and obviously will never do so if the languages are infinite.

It is possible to impose a 'normal form' on DFAs by minimising and sorting transitions: equivalence can then be determined even in the infinite case.

$\endgroup$
  • $\begingroup$ Why has this been downvoted? $\endgroup$ – NietzscheanAI Aug 8 '16 at 8:40
  • $\begingroup$ Because it doesn't answer the question $\endgroup$ – jkmartindale Nov 24 at 1:23

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.