# nerode equivalence classes q - prefix?

Lets consider the following language : $L = \{1w |w \in \Sigma^*\}$ (Alphabet is 0 and 1).

I know this language is regular, I just have to prove it now, the Problem here is the number of equivalence classes, I thought it would be: $ = \{x|x$ starts with 1$\}$ and $[\epsilon] = \{x| x$ doesn't start 1$\}$. But now I am dubious, isn't it possible for L to have 3 equivalence classes one containing words that start with 1 and one class that has epsilon as its only element?

There are three equivalence classes, and this can be seen from the minimal DFA, which has three states. The equivalence classes are $\epsilon,0\Sigma^*,1\Sigma^*$. Indeed:

• $\epsilon$ and $0$ are in different classes since $\epsilon 1 \in L$ whereas $01 \notin L$.

• $\epsilon$ and $1$ are in different classes since $\epsilon \epsilon \notin L$ and $1\epsilon \in L$.

• $0$ and $1$ are in different classes since $0\epsilon \notin L$ whereas $1\epsilon \in L$.

• All words in $\{\epsilon\}$ are clearly equivalent.

• All words in $0\Sigma^*$ are equivalent since $wz \notin L$ for all words $w \in 0\Sigma^*$ and all words $z$.

• All words in $1\Sigma^*$ are equivalent since $wz \in L$ for all words $w \in 1\Sigma^*$ and all words $z$.