patternMinor
Languages having only one Myhill–Nerode equivalence class
Viewed 0 times
myhilllanguageshavingnerodeoneclassonlyequivalence
Problem
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?
From what I understand about equivalence classes, each state is considered a class. So would $\{ a^n : n>0\}$ be the one class?
Solution
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.
Which regular languages can be accepted using a DFA having only one state?
I'm sure you can answer this one yourself.
Context
StackExchange Computer Science Q#55941, answer score: 6
Revisions (0)
No revisions yet.