3 added 135 characters in body edited Oct 5 '16 at 17:24 Shaull 13.4k11 gold badge2121 silver badges4949 bronze badges A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paperLearning Minimal Separating DFA’s for Compositional Verification, by Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable. A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paper Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable. A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as Learning Minimal Separating DFA’s for Compositional Verification, by Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable. 2 added 5 characters in body edited Jan 15 '14 at 8:31 Raphael♦ 58.9k2525 gold badges144144 silver badges327327 bronze badges A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paper Note that as @Raphel@reinierpost states, without any restrictions on A and B, the problem may become undecidable. A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paper Note that as @Raphel states, without any restrictions on A and B, the problem may become undecidable. A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paper Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable. 1 answered Jan 13 '14 at 14:39 Shaull 13.4k11 gold badge2121 silver badges4949 bronze badges A DFA as you describe is called a separating DFA. There is some literature on this problem when $$A$$ and $$B$$ are regular languages, such as this paper Note that as @Raphel states, without any restrictions on A and B, the problem may become undecidable.