edited by
11,921 views
7 votes
7 votes
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 equivalence classes here...
edited by

2 Answers

Best answer
19 votes
19 votes

No of equivalence classes as per Myhill Nerode equivalence relation = No of States in Minimal DFA 

So Draw the NFA and convert into Minimal DFA.

Strings reaching at each state in Minimal DFA, are distinguish from strings reaching at other states, that is what equivalence class mean here. 

Other things about equivalence class is that, if x and y are two strings of same class( here reaching same state), and we append some strings z to then i.e, xz and yz, that will also reach to same equivalence class (either same or any other). Minimal DFA serve our purpose. 

if we analyse the regular expression, we can see 

first state, all rejecting strings, doesn't belong to L or given regular expression.

second state, all strings ending with b or bb, means ending with b, and accepts, (a+b)*b(∊+b)

Third state, all strings ending with ba, and accepts,(a+b)*ba.

selected by
2 votes
2 votes

Meaning of equivalence classes = Minimum Number of states in DFA design.

Related questions

1 votes
1 votes
1 answer
2
Parshu gate asked Nov 27, 2017
1,314 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 ______.
4 votes
4 votes
2 answers
3
praj asked Aug 18, 2015
4,365 views
Find all the equivalence classes of Regular Language011 (0+1)* 011
0 votes
0 votes
1 answer
4
jhaanuj2108 asked Sep 26, 2018
676 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 ________.