1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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