Vtyjkyuk

Trying to solve these problems for a whole day, but just can't figure out where to start.

let $Sigma=a,b$ and $L = w inSigma^*: 3midtextlength(w)$

Define R ⊆ Σ
* × Σ
* as follows: (w, w'
) ∈ R if there is a v ∈ Σ
*
such
that: either wv ∈ L and w
'v ∉ L, or wv ∉ L and w
'v ∈ L.

Define $SsubseteqSigma^*timesSigma^*$ as the complement of $R$. That is $(w, w') in S$ iff $(w, w')notin R$.

1. State a simple rule for determining if $(w, w') in S$


2. show that $S$ is an equivalence relation


3. How many equivalence classes does $S$ have?

Any tips or direction will be much appreciated.

If I understand well then $wSw'$ iff $$textlength(w)equivtextlength(w')mod 3$$or equivlently:$$3midtextlength(w)-textlength(w')$$

This can also be expressed by: $$f(w)=f(w')$$where $f:Sigma^*to0,1,2$ is the function prescribed by $$wmapstotextlength(w)-3lfloorfrac13cdottextlength(w)rfloor$$

On base of $wSw'iff f(w)=f(w')$ it is easy to prove that $S$ is an equivalence relation:

• $f(w)=f(w)$ for all $winSigma^*$ so reflexivity.


• $f(w)=f(v)implies f(v)=f(w)$ so symmetry.


• $f(w)=f(v)wedge f(v)=f(u)implies f(w)=f(u)$ so transitivity.

The equivalence classes are the sets:

• $f^-1(0)=L$


• $f^-1(1)=vwmid vinSigmawedge win L$


• $f^-1(2)=uvwmid u,vinSigmawedge win L$