Consider the regular expression R = (a + b)* (aa + bb) (a + b)*. Which one of…
2007
Consider the regular expression R = (a + b)* (aa + bb) (a + b)*. Which one of the regular expressions given below defines the same language as defined by the regular expression R?
- A.
(a(ba)* + b(ab)*)(a + b)+
- B.
(a(ba)* + b(ab)*)*(a + b)*
- C.
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*
- D.
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)+
Attempted by 15 students.
Show answer & explanation
Correct answer: C
R = (a + b)* (aa + bb) (a + b)*
Having,
Which is equivalent to the following Transition graph [by removing transition from Q1Q1 to Q2Q2 and Q2Q2 to Q1Q1 but does not affect the accepted language, be careful] and can be converted to an equivalent regular expression as shown below.
So, equivalent regular expression is (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*
Option C is answer.