1
$\begingroup$

Consider the alphabet $\{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?

| cite | improve this question | | | | |
$\endgroup$
  • 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 '16 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 '16 at 15:38
4
$\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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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