HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Languages having only one Myhill–Nerode equivalence class

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#55941, answer score: 6

Revisions (0)

No revisions yet.