in Theory of Computation
310 views
0 votes
0 votes
$(a+b)^* =a^*(ba^*)^*$

As this identity already proved. But $a^*(ba^*)^*$ couldn't generate "bab" . But $(a+b)^*$ could generate all strings over {a,b}. Then the above identity seen to be proved false. Please discuss how this is possible.
in Theory of Computation
310 views

2 Comments

@Dhananjay15, Brother if it is already proved means it should be correct...

If we didn't get that string, it means I hope we did somewhere mistake

@Vikas Verma, added it as answer, just check it.

0
0
Let's generate bab -

(ba*)* = { ε , (ba*), (ba*)(ba*) ....... }

a*        = { ε , a, aa, aaa.....}

I am expanding (ba*)* twice i.e. (ba*)* = (ba*)(ba*)

a*(ba*)* = a*(ba*)(ba*)

                = ε(b a )(b ε )

                = bab                                         .......... [ ε .b = b or b . ε = b]
1
1

1 Answer

2 votes
2 votes
a^* (ba^*)^* =( ba^*)^* = (ba)(ba^*) = bab

Related questions