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.

  1. 2
  2. 4
  3. 5
  4. 6
in Theory of Computation by Veteran (105k points)
retagged by | 2.9k views

3 Answers

+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.
by Veteran (425k points)
+2 votes

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

by Boss (35.7k points)
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.
by Boss (25.5k points)
edited by
minimum dfa for regular expression 0*10* need 3 states then how No.of equivalence classes are 4.
yes...i missed...

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

then why it does not follow here

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 ?
No 3 is correct
@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".

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

That statement is always true- and hence called a Theorem. But there is something wrong with the question statement here.

Is this Myhill Nerode equivalence relation is in GATE syllabus?


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,505 answers
101,042 users