The Gateway to Computer Science Excellence
+2 votes
1.3k views
Find all the equivalence classes of Regular Language

011 (0+1)* 011
in Theory of Computation by (129 points)
retagged by | 1.3k views

2 Answers

+5 votes
Best answer

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 by
+2 votes

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

by Active (3.8k points)
edited by
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.

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,737 questions
57,353 answers
198,477 comments
105,248 users