1.3k views
Find all the equivalence classes of Regular Language

011 (0+1)* 011

retagged | 1.3k views

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.

by Veteran (431k points)
selected

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

by Active (3.8k points)
edited
0
where is the dead state ??
0
You dont need dead state for counting equivalnce classes.
0
@Arjun is it ?? we should reject those string which are not in the language..
+1
Yes, we need a dead state- and all strings going to dead state form its own equivalence class as per Myhill-Nerode relation. 8 should be the answer- I had missed the class for $\epsilon$.
+1
I missed it then. Thanks for clarification.