1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think you can say what you intended for (a) in the following way. Instead of merging states start with one state for each equivalence class. For each state $s$ (let's say that it corresponds to the equivalence class $S$) and each letter $t$ of the alphabet you take a word $x\in S$. Then put a transition from $s$ to the state corresponding to the class of $xt$. $\endgroup$
    – plop
    Sep 3, 2020 at 15:43
  • 1
    $\begingroup$ For $x=ab^m$ and $y=ab^n$, with $m>n$ you have $w=ab^nab^n$ which has $xw\not\in L$ and $yw\in L$. This shows that $x$ and $y$ are not in the same equivalence class. $\endgroup$
    – plop
    Sep 3, 2020 at 15:47
  • $\begingroup$ Thank you, your way to present part (a) is much clearer! And sure, making the choice of $w$ explicit was what I lacked in (b). $\endgroup$
    – Davide Leonessi
    Sep 3, 2020 at 15:52

1 Answer 1

Reset to default
0
$\begingroup$

(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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.