# Shortest string distinguishing two regular languages

Let $D_{0}$ and $D_{1}$ be two DFAs with $n$ and $m$ states, such that $L(D_{0})=L(D_{1})$.

There exist a string of length at most $n+m$ in the symmetric difference of $L(D_{0})$ and $L(D_{1})$.

We construct the following DFA $D$ from $D_{0}$ and $D_{1}$. The start state $s$ has a transition $δ(s,0)=s_{0}$ and $δ(s,1)=s_{1}$, where $s_{0}$ and $s_{1}$ are start state of $D_{0}$ and $D_{1}$.

Now $D$ represents the language ${0w∣w∈L(D_{0})}∪{1w∣w∈L(D_{1})}$. This language has at most $n+m+1$ equivalent classes in Myhill–Nerode theorem. There exist a string of length less than $n+m+1$ that differentiate state $s_{0}$ and $s_{1}$, since $s_{0}$ and $s_{1}$ can’t correspond to the same equivalent class.