11
$\begingroup$

So given two DFAs, is the problem of finding if they generate the same language a Decidable problem?

I already know that Equality of two CFL is not Decidable

but what about Equality of two DFAs? considering most of the problems with DFAs are decidable, is this decidable as well ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Yes, it is decidable in linear time drona.csa.iisc.ernet.in/~deepakd/atc-common/… $\endgroup$ – abc Sep 28 '17 at 12:16
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ Sep 28 '17 at 14:34
22
$\begingroup$

In order to decide whether the languages generated by two DFAs $A_1,A_2$ by the same, construct a DFA $A_\Delta$ for the symmetric difference $L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(A_2) \setminus L(A_1))$, and check whether $L(A_\Delta) = \emptyset$.

Here are some more details. You can construct $A_\Delta$ using the product construction: construct a product automaton, and use $(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$ as the set of accepting states.

In order to check whether $L(A_\Delta)$ is empty or not, it suffices to check whether some accepting state is reachable from the initial state, and this can be done using BFS/DFS.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Given two DFA $D_1$ and $D_2$, equality of of $D_1$ and $D_2$ and checking if $D_1$ and $D_2$ generate the same language are same things.

Yes, this problem is decidable. You can minimize both $D_1$ and $D_2$ and compare their transition functions. Given a DFA, the minimization algorithm reduces the number of states to a minimum number and this DFA is unique. Here is alternative approach.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I believe you're conflating "equivalence" of the DFAs and their equality. $\endgroup$ – einpoklum - reinstate Monica Sep 28 '17 at 13:56
  • $\begingroup$ @einpoklum yes, I use the term "equality" as a synonym of "equivalence" because the OP uses the term "Equality". $\endgroup$ – fade2black Sep 28 '17 at 14:01
  • 2
    $\begingroup$ The two are not the same, though. Even after minimization, the automata are not equal. We know them to be isomorphic, though, which is certainly decidable (if potentially harder than equality). $\endgroup$ – Raphael♦ Sep 28 '17 at 14:36

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.