-1
$\begingroup$

Is there any polynomial procedure to decide if 2 deterministic finite automatas decide the same language?

$\endgroup$
4
  • 1
    $\begingroup$ Yes, of course. This is covered in standard textbooks on automata theory. What research have you done? We expect you to do a significant amount of research before asking here, and to show us in the question what you've done (e.g., what textbooks you have consulted). You might also want to tell us what you know about automata theory (do you know the product construction? how to test whether a DFA generates the empty language?). $\endgroup$ – D.W. Jul 2 '14 at 22:32
  • 1
    $\begingroup$ See, e.g., cs.stackexchange.com/q/9130/755 (two subset tests are enough to test equivalence), or cs.stackexchange.com/q/20042/755 plus cs.stackexchange.com/q/18616/755 (computing the difference plus testing for emptyness is sufficient). See also cs.stackexchange.com/q/21897/755 and cs.stackexchange.com/q/5010/755 for more related questions. $\endgroup$ – D.W. Jul 2 '14 at 22:37
  • 1
    $\begingroup$ Hints: (1) Regular languages are closed under union, intersection, and complement, so are closed under symmetric difference. (2) Two sets are equal iff their symmetric difference is empty. (3) You can effectively determine whether the language of a finite automaton is empty. Now just fill in the details using the earlier comments' suggestions. $\endgroup$ – Rick Decker Jul 3 '14 at 1:02
  • $\begingroup$ I agree that is duplicated question, because the other is equivalent, but how could I see that? I was looking for "the same" language... I cannot serach for all possible equivalent way of writing the question... Anyway sorry! $\endgroup$ – Jody Jul 3 '14 at 7:23
1
$\begingroup$

Let $D_1,D_2$ be the automata in question, and let $L_1,L_2$ be the corresponding languages. Using standard construction one can construct an automaton $D$ for $L_1 \triangle L_2$ (the symmetric difference of $L_1$ and $L_2$), and then one checks whether this automaton accepts any words.

$\endgroup$
2
  • $\begingroup$ Ok, thank you, but anyway should I check all the possible words one by one? Because in this way I am not sure it will be polynomial.. $\endgroup$ – Jody Jul 3 '14 at 7:20
  • $\begingroup$ @Jody No, there is a different way of determining whether a DFA (or even an NFA) accepts any words. $\endgroup$ – Yuval Filmus Jul 3 '14 at 15:27
1
$\begingroup$

By Myhill-Nerode, the minimal DFA for a regular language is unique. You can minimize both and check that they are equal.

$\endgroup$

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