# 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: $[1] = \{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?

Thanks in advance

## 1 Answer

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$.