retagged by
4,356 views

2 Answers

Best answer
7 votes
7 votes

First of all we should specify which "equivalence relation". Since not specified, I assume based on Myhill-Nerode relation. 

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

Class No. Strings
1 $\epsilon$
2 0
3 01
4 011
5 0110, 01100, 01110, ...- all strings starting with 011 and ending in 0
6 01101, 011001, 011011, ... -all strings starting with 011 and ending with 01
7 011011, 0110011, 0111011, ... -all strings starting with 011 and ending with another 011. 
8 All strings not starting with 011

Totally 8 equivalent classes- the last one for a dead set of strings (can never be in language after appending any string). So, the min-DFA for $L$ will have 8 states with one being a dead state. 

selected by
2 votes
2 votes

7 states + 1 dead state which I missed. $\Rightarrow$ 8 classes . You can verify with partioning method.

edited by

Related questions

7 votes
7 votes
2 answers
2
resuscitate asked Dec 5, 2015
11,914 views
The number of equivalence classes which exist for the following regular expression R are ______. $R=(a+b)^*b(a+b+\epsilon )$ what is the meaning of equivale...
1 votes
1 votes
1 answer
3
Parshu gate asked Nov 27, 2017
1,312 views
Consider a regular language L over Σ={0,1} such that L contains every string which ends with "0". The number of equivalence classes in L is ______.
0 votes
0 votes
1 answer
4
jhaanuj2108 asked Sep 26, 2018
675 views
Consider the following DFA: The number of distinct sets present in all partitions while converting given DFA into minimal DFA using Myhill-Nerode theorem is ________.