edited by
648 views
1 votes
1 votes
How does the regular expression (a+b)*=(a*b*)* hold true? Please  explain  with an  example.
edited by

2 Answers

0 votes
0 votes

good question 

(a+b)*=(a+b)(a+b)......(a+b) { repeated any number of times including 0 times }  so it can give expression like   null  or a or b , aa or bb  or aaa... or bbb... or  aaabbababbbbaaa... (means either a or b in each term)

(a*b*)*=(a*b*)(a*b*)...... (any no of times ) so  it can give expression like   null  or a or b or aa or bb or abab

or aaabbbababaaaa like string  means exactly same strings which are produced by above 

0 votes
0 votes

Firstly , let's talk about (a+b)* , you might be knowing that it's a Universal language to generate all strings over {a,b}.

Now , to prove (a+b)*=(a*b*)*,

  • we will start with the minimal string that is null string.Both of them produces it with *.
  • 1-Length strings, a,b can also be produced by both.
  • 2-Length strings aa,ab,ba,bb can also be produced by both.
  • n-Length strings aaaaa.......,ababa......,bbbbb.......... can be produced by both.

like wise , take one string that is definitely produced by(a+b)*, just compare and conclude whether the same can be produced by (a*b*).

Conclusion: After a decent number of comparisons we can conclude that both the expressions are producing same strings.