Distinguishable Pair

Distinguishable pairs are a pair of strings that can be prepended onto any string, and will result in one of them belonging to a language, while the other does not. Non-distinguishable pairs either both belong to a language or are both rejected. More stronger, prepending a non-distinguishable pair to any string will make the resulting pair either both accepted or both rejected.

Definition §

Distinguishable Pair ^definition

Let $L$ be a language. Let $x,y,z$ be formula that do not necessarily have to belong to $L$. Then, $x$ and $y$ are distinguishable in $L$ iff:

$$\exists z\text{ s.t.}\{\begin{array}{l}x\circ z\in L\wedge y\circ z\notin L\text{ OR}\\ x\circ z\notin L\wedge y\circ z\in L\end{array}$$

• $z$ is known as the distinguishing suffix
• The distinguishing pair is represented as $(x,y)$

Again, a distinguishable pair for a language need not necessarily belong to the language!

That is, we could have a distinguishable pair $(x,y)$ for $L$ with both $x\notin L$ and $y\notin L$

Theorems §

T1: A DFA has unique resultant states for a distinguishing pair ^t1

Let $L$ be a language and $M$ be a DFA. For every distinguishing pair $(x,y)$ in L:

$$\text{M recognises L}⟹q(x)\ne q(y)$$

• See the definition of a DFA recognising a language here.
• $q(x)$ is resulting state after applying the extended transition function on $q_0$ (the initial state of $M$) with the string $x$

This means any DFA needs at least 2 states to recognise $L$, if $L$ contains a distinguishing pair.

Proof

From the memorylessness lemma:

Then, for the FSA, $M$, we can use a proof by contrapositive:

The contrapositive of the memorylessness lemma states that:

$$q(x\circ z)\ne q(y\circ z)⟹q(x)\ne q(y)$$

If $q(x)=q(y)$ means that $M$ either accepts both $x$ and $y$ or rejects both $x$ and $y$, then the negation of this would mean that $M$ accepts one and rejects the other.

So if we assume that $M$ accepts one of $x\circ z$ or $y\circ z$ and rejects the other, we get a language, $L$ generated by $M$ where one of $x\circ z$ or $y\circ z$ is in $L$ and the other one is not.

This is our definition of a distinguishable pair!

So, if we assume a distinguishable pair, then it implies that $q(x)\ne q(y)$, which is what we set out to prove.

C1: A language with a distinguishing pair cannot be recognised by the single-state FSA

From theorem 1, a DFA recognising $L$ where $L$ has a distinguishing pair need at least two states. Then, the single-state FSA (having only one state) cannot recognise it.

Examples §

Distinguishable & Non-distinguishable pairs

Let $L$ be the language given by:

$$L=(0\circ 1{)}^{\ast }=\{ϵ,01,0101,010101,\dots \}$$

• Are the strings $0$ and $1$ distinguishable in $L$?

• Are the strings $01$ and $0101$ distinguishable in $L$?

Solution

1. We can use the distinguishing suffix $z=1$:

• $01\in L$
• $11\notin L$

Hence, $0$ and $1$ are distinguishing pairs in $L$.

2. We can try to find a distinguishing suffix. If none exist, the pair must be non-distinguishable.

First, note that $z=ϵ$ would be essentially just taking the strings ‘as is’. In this case they are both in $L$, so that won’t work.

If we take $z$ as anything but $(01{)}^{\ast }$, attaching it to the ends of $01$ and $0101$ would make them both not belong to $L$.

But if $z$ is $(01{)}^{\ast }$, (for example, $z=01$) then attaching it to the end would make:

• $0101\in L$
• $010101\in L$

So there is no possible suffix and the strings are non-distinguishable in $L$