1
$\begingroup$

Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time.

My idea is this: Let's say WLOG that $M_1$ has 1 accepting state. We run DFS from that state and look at paths from the state to a starting state. Ideally, a path will be of the form $abb (a\cup b)abbb(ba)^*$ The "or" operator will be used in places where the "path" from the root to the leaf node splits and then merges, and the "*" operator will be used in case of cycles. We can then do the same thing for $M_2$ and then do an intersection of their paths to find if they have any common paths.

This is basically just an idea that I had; I'm not too sure about the fine details, like how cycle detection will work, and if I need to modify DFS a bit for this to actually work.

Am I totally wrong? Are there any issues with this algorithm? Any help would be appreciated.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ You are roughly converting the automata into two regexps. That does not look very useful to me. I'd try to exploit some closure properties, instead. $\endgroup$
    – chi
    Apr 10, 2017 at 15:30

1 Answer 1

Reset to default
0
$\begingroup$

You want to know if there is any string accepted by both automata. There are standard techniques for producing an automaton that accepts exactly these strings, and there are standard techniques for seeing if the resulting automaton accepts any strings.

Improve this answer
$\endgroup$

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