The Art Gallery Guardian

Shortest string distinguishing two regular languages


Let D0D_0 and D1D_1 be two DFAs with nn and mm states, such that L(D0)L(D1)L(D_0)\neq L(D_1).

There exist a string of length at most n+mn+m in the symmetric difference of L(D0)L(D_0) and L(D1)L(D_1).

We construct the following DFA DD from D0D_0 and D1D_1. The start state ss has a transition δ(s,0)=s0\delta(s,0) = s_0 and δ(s,1)=s1\delta(s,1) = s_1, where s0s_0 and s1s_1 are start state of D0D_0 and D1D_1.

Now DD represents the language {0wwL(D0)}{1wwL(D1)}\set{0w|w \in L(D_0)} \cup \set{1w|w\in L(D_1)}. This language has at most n+m+1n+m+1 equivalent classes in Myhill–Nerode theorem. There exist a string of length less than n+m+1n+m+1 that differentiate state s0s_0 and s1s_1, since s0s_0 and s1s_1 can't correspond to the same equivalent class.

Posted by Chao Xu on .
Tags: DFA.