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?

closed as unclear what you're asking by D.W., David Richerby, Juho, Luke Mathieson, lPlant May 25 '15 at 3:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '15 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 '15 at 17:30
  • $\begingroup$ We haven't learned about minimal DFA I am afraid.. $\endgroup$ – Elimination May 21 '15 at 9:03

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