Let a language, $L$ such that the equivalence relation, as defined in MyhillNerode theorem has $4$ equivalence classes; $A_1, \ldots, A_4$.Let $S = A_1 \cup A_2$. Is $S$ always regular?How many equivalence classes does the relation $\sim S$ creates?I think we may construct two DFA's, $D_1, D_2$ which accept $A_1, A_2$, respectively. Let $D$ to be the DFA accepting $L$. We construct $D_1$ by copying the states of $D$. We choose arbitrary $w\in A_1$ and run it on $D$. We mark as accepting state only the state which accepted the $w$. Same applied for $D_2$.Finally, we unite $D_1$ and $D_2$ be connecting a new starting state and two $\varepsilon$ arrows to each DFA. So we constructed in that way an NFA and therefore $S$ is a regular language. Is this construction legal?My thought is $3$ because every word can be either at $S, A_3, A_4$. Am I right?
union of two equivalence classes (MyhillNerode theorem)
formal languages;regular languages
... Is this construction legal?The construction is legal, but it isn't guaranteed to recognize $S=A_1\cup A_2$. The problem is that $D_1$ and $D_2$ don't necessarily recognize $A_1$ and $A_2$. But they recognize them if $D$ is the minimal DFA recognizing $L$. But you are making your live unnecessary complicated anyway. You could just mark the states corresponding to $A_1$ and $A_2$ as the accepting states, and you have your DFA recognizing $S=A_1\cup A_2$.My thought is 3 because every word can be either at $S$, $A_3$, $A_4$. Am I right?No, at least this argument is not convincing. The DFA constructed above still has 4 states, so we only know that it cannot be more than 4. We also know that it must be more than one, which leaves 2, 3, and 4 as possible answers. My own guess would be actually 4, but I assume here that $A_1$ and $A_2$ are just two arbitrary equivalence classes, i.e. that the indices have no significance.