Question

Consider the following regular expression
I. (a +b)* abb (a + b)*
II. (a + b)* a(a + b)* bb (a + b)*
III. (a + b)* ab (a + b)* b(a + b)*
IV. (a + b)* abb (a + b)* a
Which of the above regular expressions are equivalent?

• A. I, III and IV only
• B. I, II an III only
• C. I and II only
• D. II, III and IV only

Answer 1

The correct option is C I and II only

I and II generate all strings containing abb as a substring. However in III, abab is accepted which should be a non member if it has to accept abb as substring. IV is also wrong because it not only wants abb as substring, every string should also end with 'a'. Hence the answer is options (d).