The Gateway to Computer Science Excellence

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,505 answers

195,555 comments

101,042 users