The Gateway to Computer Science Excellence

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

- 2
- 4
- 5
- 6

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

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

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.

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.

0

No of equivalence classes as per Myhill Nerode equivalence relation = No of States in Minimal DFA ,

then why it does not follow here

0

i think no. of equivalence classes here is 4 only

string starting with 0 , 0 0.........

string starting with 0 , 0 0........and end with exactly one 1 , exactly one 1 can also come here .

string starting with 1 and followed by 0's.

a dead state

so 4 equivalence class but 3 states in min. dfa

Tell me where i am wrong ?

string starting with 0 , 0 0.........

string starting with 0 , 0 0........and end with exactly one 1 , exactly one 1 can also come here .

string starting with 1 and followed by 0's.

a dead state

so 4 equivalence class but 3 states in min. dfa

Tell me where i am wrong ?

+1

@Akansha classes 2 and 3 are the same as far as equivalence class as per Myhill-Nerode theorem is concerned. That relation consider only the "remaining part of string".

0

Arjun Sir , Am i right now ?

Equivalance class -

1st --> string starting with 0 and 0000........

2nd --> string having exactly one 1 , it can be of the form -- 0001 , 10000 , 1 etc

3rd --> dead state

Sir 1 doubt

No of equivalence classes as per Myhill Nerode equivalence relation = No of States in Minimal DFA

is always true na..

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

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

52,345 questions

60,522 answers

201,950 comments

95,372 users