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

Can you please explain ?

  • $\begingroup$ Did you draw a totally defined DFA? Recall that $R_{M}$ is defined on $\Sigma^{*} \times \Sigma^{*}$, where $\Sigma$ is your alphabet. $\endgroup$ – ml0105 Jan 3 '17 at 0:51
  • $\begingroup$ @ml0105, totally defined DFA? I heard it first time. I newbie with that. $\endgroup$ – Mithlesh Upadhyay Jan 3 '17 at 0:55
  • $\begingroup$ 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. $\endgroup$ – ml0105 Jan 3 '17 at 0:59
  • $\begingroup$ @ml0105: Yes, it’s fully defined with three states. $\endgroup$ – Brian M. Scott Jan 3 '17 at 1:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jan 3 '17 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.