Distinguishing words for states and for prefixes

Let $D=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ be a DFA with extended transition function ${\delta }^{\ast }$.

• A word $x\in {\mathrm{\Sigma }}^{\ast }$ distinguishes states $p,q\in Q$ when exactly one of the states ${\delta }^{\ast }(p,x)$ and ${\delta }^{\ast }(q,x)$ is accepting. Equivalently, $x$ witnesses that $p$ and $q$ are not state-equivalent.

• For a language $L\subseteq {\mathrm{\Sigma }}^{\ast }$, a word $x\in {\mathrm{\Sigma }}^{\ast }$ distinguishes words $u,v\in {\mathrm{\Sigma }}^{\ast }$ when exactly one of $ux$ and $vx$ lies in $L$. Equivalently, $x$ witnesses that $u\mathrm{̸}{\equiv }_{L}v$.

• Distinguishing words are the concrete witnesses behind both minimization and Myhill--Nerode lower bounds.

• The empty word $\epsilon$ is allowed; it distinguishes two states exactly when one is accepting and the other is not.