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.
Detemine if two DFA's are non-disjoint in polynomial time?
algorithms;automata;polynomial time
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.