3
$\begingroup$

Consider the alphabet $\Sigma = \{a,b\}$. For which languages does the Myhill–Nerode equivalence relation have exactly one class?

From what I understand about equivalence classes, each state is considered a class. So would $\{ a^n : n>0\}$ be the one class?

$\endgroup$
3
  • 2
    $\begingroup$ Welcome to CS.SE! Please proof-read your question. There appear to be some typos, which makes your question hard to read. Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Also, we don't want to be an answer-checking service; we want to help you understand concepts, not do your exercise or check your solution for you. Can you edit the question to elaborate on what you've tried, and specifically what prevents you from being sure of your answer? $\endgroup$
    – D.W.
    Apr 13, 2016 at 22:22
  • $\begingroup$ It should be: "for which languages does the Myhill–Nerode equivalence relation have exactly one class?" $\endgroup$
    – A.Schulz
    Apr 14, 2016 at 15:38
  • $\begingroup$ Your example needs three states. aaa would be in an accepting state, eps and aba wouldn’t. You can move from eps to an $\endgroup$
    – gnasher729
    Feb 15 at 18:50

2 Answers 2

6
$\begingroup$

Assuming that you mean the Myhill-Nerode relation, the Myhill-Nerode theorem states that the number of equivalence classes exactly equals the number of states in the minimal DFA accepting the language (if it's regular; otherwise there are infinitely many equivalence classes). So we have reduced the question to the following one:

Which regular languages can be accepted using a DFA having only one state?

I'm sure you can answer this one yourself.

$\endgroup$
2
$\begingroup$

Let $L \subseteq \{ a, b\}^*$ be a language with one Myhill-Nerode equivalence class. You can show that $L$ must be trivial, that is $L\in \{\emptyset, \{a, b\}^*\}$, either by using the Myhill-Nerode theorem as Yuval did, or by showing that directly. Indeed, as for $L$ to have a single Myhill-Nerode equivalence class, it means that for all three words $x,y$ and $z$ over $\{ a, b\}$, it holds that $$x\cdot z \in L \Longleftrightarrow y\cdot z \in L$$

In words, we cannot separate any two words $x$ and $y$, by any word $z$. Hence, $L$ must be trivial, because otherwise there are two words $x\in L$, and $y\notin L$, and for $z = \epsilon$, we get that $x \cdot z = x \in L$, but $y\cdot z = y \notin L$, and we have reached a contradiction.

$\endgroup$

Your Answer

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

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