retagged by
7,165 views
3 votes
3 votes

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 that are reachable from the start state. $R_M$ has ___ equivalence classes.

  1. 2
  2. 4
  3. 5
  4. 6
retagged by

8 Answers

0 votes
0 votes
No of equivalence classes is the no.of states in minimum dfa..

Given language is " SRT of strings which contains exactly one 1"

For that we need 3 states so No.of equivalence classes are 3 with dead state.
edited by
0 votes
0 votes
number of equivalnce classes in a FA is equal to the number of states in the minimal dfa . so the answer is 3

hint of dfa: the above language is " strings over {0,1}* where number of 1's are exactly  1 "

edit:  the question seems to ask  the relation defined by M as  "RM" - which is the  the relation over (0+1)* ( as domain) to  0*10* as range . now total class are 3 out of which only one  class is right ( one with final state) so the anser could be  1 if that is what its asking. now the relation is in itself contradictory when it says all the states reachable from start state which means union of all the class ( as all the 3 states are reachcble from the start state )  which is as we know comes out to be (0+1)* thus the answer is 1. else it may say that the number of class reachable from start state in which case all the states of DFA are reachable thus its equal to number of states which is 3.
0 votes
0 votes

3 is right

0 votes
0 votes
Relation RM  ='all states are reachable from the start state'

only 3 states required including dead state.

Let q0 be a start state and  q2 is dead state

δ:Q×Σ→Q which implies q0 x {0,1} → {q0 , q1, q2)

δ(q0,0)=q0==>for 0* reached to q0         (qo to q0)

δ(q0,1)=q1==>for 0*1 reached to q1        (q0 to q1)

δ(q1,0)=q1==>for 0*10* reached to q1      (q0 to q1)

δ(q1,1)=q2==>for 0*10*1 reached to q2     (q0 to q2)

δ(q2,0)=q2==>for 0*10*10* reached to q2   (q0 to q2)

δ(q2,1)=q2==>for 0*10*11* reached to q2   (q0 to q2)

Hence, There are 6 equivalence classes
Answer:

Related questions