FOR FREE CONTENT

Select the correct regular expression of the given machine

 

 

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

 

Answer: 

 

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.