edited by
3,047 views
4 votes
4 votes

R= a*b* + b*a*

  1. How many final states exist in the minimized DFA that accepts a language equivalent to R.
  2. How many equivalence classes of ∑ to represent a language which is equivalent to R.
edited by

1 Answer

3 votes
3 votes

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)
edited by

Related questions

1 votes
1 votes
1 answer
1
Kshitij Hansda asked Sep 15, 2018
1,734 views
Consider the following regular expressionR=(a+b)* (a+b+ε)awhich of the following is equivalent to the abovea)(a*+b*)+ (aa+ba)b)(ε+a+b*)+ ac)(a+b)+ (a+b+ε)ad)None of th...
1 votes
1 votes
2 answers
2
gate chintu asked Jun 16, 2015
9,603 views
Consider following Regular Expression(i) a*b*b (a+ (ab)*)* b*(ii) a*(ab + ba)* b*What is length of shortest string which is in both (i) & (ii)?A. 2 B. 3 C. 4 D. None