An algorithm to check if two DFA are disjoint What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.
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.