Question:
Let L be a regular language, ~${_L}$ is it's equivalence relation (as was defined in Myhill Nerode theorem) that divides $\Sigma^* $ to 4 non empty equivalence classes A1, A2,A3,A4. Let $S=A1 \cup A2$. Prove that S is regular and that it's equivalence relation ~${_S}$ always induces between 2 and 4 equivalence classes.
Thoughts
I don't understand something here. How come there can be more than 2 classes? We just threw 2 out, didn't we? And how come this number can vary?
Best Answer
Think about it in terms of finite state automata. Since $\sim_L$ has $4$ equivalence classes, a minimal FSA $M$ for $L$ has $4$ states, say $q_1,q_2,q_3$, and $q_4$, such that $A_k$ is the set of words in $\Sigma^*$ that cause $M$ to end in state $q_k$ for each $k=1,2,3,4$. $S$ is then the set of words that cause $M$ to end in state $q_1$ or state $q_2$.
If you’ve answered that first question correctly and understand the relationship between Myhill-Nerode equivalence classes and states of DFAs, it should be clear why $\sim_S$ has at most $4$ classes. But the DFA that you have for $S$ may not be minimal, so you may be able to reduce the number of classes. Here’s a concrete example.
One question still remains: