# Detemine if two DFA's are non-disjoint in polynomial time?

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.

• 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. – chi Apr 10 '17 at 15:30