Shortest string distinguishing two regular languages
Let and be two DFAs with and states, such that .
There exist a string of length at most in the symmetric difference of and .
We construct the following DFA from and . The start state has a transition and , where and are start state of and .
Now represents the language . This language has at most equivalent classes in Myhill–Nerode theorem. There exist a string of length less than that differentiate state and , since and can’t correspond to the same equivalent class.