The Art Gallery Guardian

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.

Posted by Chao Xu on .
Tags: DFA.