1
$\begingroup$

What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.

$\endgroup$
1
$\begingroup$

Construct the intersection DFA of both DFA's. Then, check if there is a path from the starting state to any end state.

If there is a path, then the two DFA's are not disjoint. If there isn't, then they are.

$\endgroup$
5
  • $\begingroup$ Intersection can be defined in terms of complementation and union cs.um.edu.mt/gordon.pace/Research/Software/Relic/… Maybe it will be useful for somebody like me. $\endgroup$
    – Oleg Dats
    Apr 20 '21 at 17:02
  • $\begingroup$ Is there an algorithm to construct a few DFA that are disjoint for a given DFA? $\endgroup$
    – Oleg Dats
    Apr 20 '21 at 17:16
  • $\begingroup$ What do you mean by that? If I understand correctly, construction the complement DFA will work $\endgroup$
    – nir shahar
    Apr 20 '21 at 17:25
  • $\begingroup$ yes, construction the complement DFA will work. I am interested to generate few more. For example: given 1+ the desired set of DFA = {2+, 10+, 01+,...}. All of them are disjoint with 1+ $\endgroup$
    – Oleg Dats
    Apr 20 '21 at 17:27
  • 1
    $\begingroup$ Enumerate over all DFA's and for each one of them intersect it with the complement DFA. $\endgroup$
    – nir shahar
    Apr 20 '21 at 17:30

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.