1) a*b* +b*a* must have 6 states . Among them 5 will be final states
2) Please Refer this link --> https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
Myhill–Nerode theorem (Wikipedia)
the existence of a finite automaton recognizing L implies that the Myhill–Nerode relation has a finite number of equivalence classes, at most equal to the number of states of the automaton, and the existence of a finite number of equivalence classes implies the existence of an automaton with that many states.
Simply speaking, the number of equivalence classes for a language L will be the SAME as the number of states in minimal DFA of L.
Two strings are equivalent with respect to a language if whenever we append to them some string over the alphabet, the resulting strings either both belong to the language or both are outside the language.
Such group of strings with similar behavior belongs to one class.
- In minimal DFA of given L has 6 states
- So L has 6 equivalence classes.
- We can find the equivalence class of strings by seeing the min DFA and collecting the set of strings reaching each of the state in it.
- Otherwise, we can proceed intuitively like this:
1. After seeing the regular expression we know that strings in L are either all a's followed by a b or all b's followed by an a. So, equivalence classes will be
strings containing only a |
strings containing only b |
strings of the form aa*bb* |
strings of the form bb*aa* |
empty string |
any other string (corresponding to dead state) |