Let$\mathit{x}\mathit{a}\mathit{n}\mathit{d}\mathit{y}$ be strings and let L be any language. We say that x and y are distinguishable by L if some string Z exists whereby exactly one of the strings$\mathit{x}\mathit{z}\mathit{a}\mathit{n}\mathit{d}\mathit{y}\mathit{z}$ is a member of L ; otherwise, for every string z , we have $\mathbf{xz}\mathbf{\in }\mathit{L}$whenever $\mathit{y}\mathit{z}\mathbf{\in }\mathit{L}$and we say that are indistinguishable by L. If $xandy$are indistinguishable by L, we write x ≡L y. Show that$\mathbf{\equiv }\mathit{L}$is an equivalence relation.

An equivalence relation is a relationship on a set, generally denoted by “∼”, that is reflexive, symmetric, and transitive for everything in the set.

The relation “is equal to”, denoted$=$ , is an equivalence relation on the set of real numbers since for any

1. (Reflexivity) $x=x$

2. (Symmetry) if $x=ytheny=x$

3. (Transitivity) if $x=yandy=zthenx=z$

Consider an alphabet$\Sigma .Letx\in {\Sigma }^{*};Fory\in \Sigma$

$xy\in Lifanonlyifxy\in L$

So, X is indistinguishable to X and X is arbitrary.

Therefore, $\equiv L$is reflexive

Suppose $x{\equiv }_{L}y$ . This implies that for all $z\in \sum ^{*},$

1. $xz,yz\in Lorxz,yz\notin Lforallz\in \sum ^{*}.$
2. $yz,xz\in Loryz,xz\notin Lforallz\in \sum ^{*}$

The implication in $\left(2\right)meansy{\equiv }_{L}x.$

Thus, $\equiv L$is symmetric.

Consider $x,y,z\in {\Sigma }^{*},x\equiv Ly,andy\equiv Lz.$

To prove transitivityshow that $x\equiv Lzoru\in {\Sigma }^{*},xu\in L$if and only$ifzu\in L.$ Consider that $u\in {\Sigma }^{*}andxu\notin L.$ Now, $yu\in Landzu\in Lbecausex\equiv Lyandy\equiv Lzy$respectively. Also, $xu\notin L.Fromx\equiv Ly,y\equiv Lz,$it is concluded that $yu\notin Landzu\notin L.xu\in L$if and only if $zu\in L.Itistruethatx\equiv Lz.$

Because $x,y,andz$are arbitrary, $\equiv L$is transitive.