The Gateway to Computer Science Excellence
+2 votes

(a*b*)* = (a + b)*
I always used this while solving questions. It seems correct also because when ever I pick a random string over {a, b} then I found that it can be generated from (a*b*)*. But I don't have any formal proof for this.

Someone, please proof this.

in Theory of Computation by Boss (16.5k points) | 1.3k views
These two are equivalent expressions.If you construct FA for the LHS  ,then the same FA can also be used for RHS or vice versa. So two machines are equivalent iff languages generated by them are same.I dont know other way to proof this:(

you can prove it like this,

(a*b*)* = ((a* + a + ϵ)(b* + b + ϵ))*

           = (a*b* + a*b + a* + ab* + ab + a + b* + b + ϵ)*  // opening brackets

           =(a*b* + a*b + a* + ab* + ab + b* + ϵ +  a+ b)*   // rearranging and placing a + b at last

           =(a + b)* // you know why..

Thank you @joshi_nitish
@joshi (a*b* + a*b + a* + ab* + ab + b* + ϵ +  a+ b)* this leads to (a+b)* how?

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,364 answers
105,260 users