1 votes 1 votes How comes 3 states i got 4 states Theory of Computation bad-question + – Deepalitrapti asked Jun 5, 2019 Deepalitrapti 889 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Deepalitrapti commented Jun 5, 2019 reply Follow Share But its not a minimal dfa 0 votes 0 votes prashant jha 1 commented Jun 6, 2019 reply Follow Share You don't need to draw DFA for this problem . If we see the regEx itself , on expanding. $R=(a+b)^{*}ba+(a+b)^{*}b+(a+b)^{*}$. Thus according to the regEx , the language accepted will be all the strings on $\sum^{*}$ concatenated with a 'b' , concatenated with 'a'. All the strings of $(a+b)^{*}$ will be in either $(a+b)^{*}a$ or $(a+b)^{*}b$ . So there must be 2 equivalence classes . Right? But we've forgotten about $\epsilon$ ,since $\epsilon$ is also present in the language . Thus , there are 3 equivalence classes. 0 votes 0 votes ajayjain024 commented Jun 9, 2019 reply Follow Share Hi , Can you please explain what do equivalence classes mean? 0 votes 0 votes Arjun commented Jun 9, 2019 reply Follow Share So sad to see GATE aspirants going behind such questions. How many grammatical mistakes does this question have? What is meant by "equivalence class" for a regular expression? Do whatever you want but you wont be posting such questions in GO anymore -- "you" means "no one". 3 votes 3 votes prashant jha 1 commented Jun 10, 2019 reply Follow Share I saw this question in some book too , some study material of some institute. @ajayjain024 https://en.wikipedia.org/wiki/Equivalence_class Equivalence relation is required to define equivalence classes , here in this question i think they wanted to ask what are the different types of strings being represented by regEx and confusing them with equivalence classes. 0 votes 0 votes Please log in or register to add a comment.