4 votes 4 votes Find all the equivalence classes of Regular Language 011 (0+1)* 011 Theory of Computation regular-language myhill-nerode + – praj asked Aug 18, 2015 retagged Jul 4, 2017 by Arjun praj 4.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Arjun answered Aug 18, 2015 selected Aug 18, 2015 by Pooja Palod Arjun comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 7 states + 1 dead state which I missed. $\Rightarrow$ 8 classes . You can verify with partioning method. Mojo-Jojo answered Aug 18, 2015 edited Aug 19, 2015 by Mojo-Jojo Mojo-Jojo comment Share Follow See all 5 Comments See all 5 5 Comments reply Aditya commented Aug 19, 2015 reply Follow Share where is the dead state ?? 0 votes 0 votes Mojo-Jojo commented Aug 19, 2015 reply Follow Share You dont need dead state for counting equivalnce classes. 0 votes 0 votes Aditya commented Aug 19, 2015 reply Follow Share @Arjun is it ?? we should reject those string which are not in the language.. 0 votes 0 votes Arjun commented Aug 19, 2015 reply Follow Share 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 votes 1 votes Mojo-Jojo commented Aug 19, 2015 reply Follow Share I missed it then. Thanks for clarification. 1 votes 1 votes Please log in or register to add a comment.