Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Question

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is an equivalence relation.

Let $I(L)$ be the number of equivalence classes of $\equiv_L$

(a) Suppose $L$ is a language and $I(L)$ is finite. Construct a DFA recognizing $L$ that has exactly $I(L)$ states.

(b) Consider the language $L = \{www : w \in \{a,b\}^*\}$. Show that $L$ is not regular by giving infinitely many pairwise inequivalent elements. [which is something proven to work earlier]

---

Now, for (a) I think I got a reasonable solution, for (b) I don't feel so sure.

For part (a) I describe an algorithm which first creates a start state for the DFA and labels it $\bar\varepsilon$, i.e. the $\equiv_L$-equivalence class of $\varepsilon$. Second, for each letter $a$ in the input alphabet a new state $\bar a$ is created and a transition from $\bar\varepsilon$ to $\bar a$ is labelled $a$. Then all the states with the same label are merged in a single state, and the transitions are adjusted as a consequence. Hence, this procedure just carried on $\bar\varepsilon$ is iterated to each state just added. The algorithm stops when an iteration does not add any new state or transition.

Do you think that the writer wanted me to use this much information about $\equiv_L$-equivalence classes or there is a neater solution?

For part (b), I believe that all the words generated by $ab^*$ are pairwise not $\equiv_L$-equivalent, with that $L$. Am I not sure I can justify it further than this, but is there another simpler example?

Thank you for any help, this is a rather long question.

Answer 1

(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\epsilon$, the accepting states to be the classes of the words in $L$. For each pair of states $s_1,s_2\in \Sigma^*/\equiv_L$ and letter $t\in\Sigma$ we will have the value of the transition function $\delta(s_1,t)=s_2$ if and only if for a word (equivalently, for all words) $x\in s_1$ we have that the word $xt\in s_2$.

(b) The examples that you showed work. The classes of the words $ab^n$, for $n=1,2,...$ are all different. In fact, if $x=ab^m$, $y=ab^n$ and $m>n$, then taking $w=ab^nab^n$ we get that $xw\not\in L$, while $yw\in L$. Therefore, $x\not\equiv_L y$.