Select the correct regular expression of the given machine



  1. (ab + aba)*
  2. (ab + abab)*
  3. (ab + aba + abab)*
  4. None




From the given machine it is clear that λ is accepted because initial state S is final state. Now by input ‘ab’ we reach another final state B   and by input ‘aba’ we reach another final state C.


So, we can also get final state by the combination of input ‘ab’ and ‘aba’. 


Regular Expression RE = (ab + aba)*

But here a and c is correct answer

Because (ab + aba)* = (ab + aba + abab)* 


Both are equivalent because as we know,

(a + b)* = (a + b + ab)* = (a* + b)* = (a + b*)* = (a + b*)* = (a*b*)* 

If we calculate the regular expression of final state it will be (λ + ab + aba + abab + abaab)* 


So, overall we can say it (ab + aba)* 

So, answer is a. and though a. and c. is same so, answer is a. and c.