# Find equivalence classes of given regular expression

Let $L$ be the language generated by regular expression $0^*10^*$ and accepted by the deterministic finite automata $M$. Consider the relation $R_M$ defined by $M$. As all states are reachable from the start state, $R_M$ has ________ equivalence classes.

### My Try:

If we draw the DFA for this language then it will have $3$ state, where one is final state and two are non-final states. Then answer should be $3$.

But, official answer is given $6$.

• Did you draw a totally defined DFA? Recall that $R_{M}$ is defined on $\Sigma^{*} \times \Sigma^{*}$, where $\Sigma$ is your alphabet. – ml0105 Jan 3 '17 at 0:51
• Frequently, we draw FSMs where the edges only handle the transitions we need to accept the language $L$, and omit the others. In reality, the transition function $\delta : Q \times \Sigma \to Q$ is a total function. So for each (state, letter) pair, you should have a directed edge in your DFA. This is what I mean by a totally defined DFA. – ml0105 Jan 3 '17 at 0:59
• @Mithlesh: The relation that I have in mind is the one that says that words $x$ and $y$ are related if they take $M$ to the same state when it starts in the initial state. – Brian M. Scott Jan 3 '17 at 1:17