Let a language, $L$ such that the equivalence relation, as defined in Myhill–Nerode theorem has $4$ equivalence classes; $A_1, \ldots, A_4$.

Let $S = A_1 \cup A_2$.

  1. Is $S$ always regular?
  2. How many equivalence classes does the relation $\sim S$ creates?
  1. 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?
  2. My thought is $3$ because every word can be either at $S, A_3, A_4$. Am I right?
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$
    – Raphael
    May 20, 2015 at 16:09
  • $\begingroup$ Are you aware of the relation between the Myhill-Nerode classes and the minimal DFA? How is the relation $\sim S$ defined? I am not sure I understand what you mean. $\endgroup$
    – babou
    May 20, 2015 at 17:30
  • $\begingroup$ We haven't learned about minimal DFA I am afraid.. $\endgroup$ May 21, 2015 at 9:03

1 Answer 1


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


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