Redirected
retagged by
7,175 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

4 votes
4 votes
Here $M$ is a DFA for $L$. It is not mentioned that $M$ is a minimal DFA.

$R_M$ is defined by $M$ as the set of states reachable from the start state.

What does this mean? All reachable states form 1 class and other form another class? In this case answer must be 2.

PS: This question is not in any way related to Myhill-Nerode Theorem as first of all DFA is not minimal, and then Myhill-Nerode theorem talks about equivalence relation which is defined using a specific RELATION based on appending a string and reaching final state or not. It is not applicable on any other equivalence class/relation.
1 votes
1 votes

The no of equivalence class will be the no of states in the minimal dfa .

In the above dfa design there will be three states only so answer is 3 .

edited by
1 votes
1 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