I'm a student learning regular expression. today while studying I saw the question
Regular expression (A*B*)* = (A+B)* proof.
for me + notation means one or more, while * means zero or more.
So $(A^*B^*)^*$ accepts $A$ but $(A+B)^*$ doesn't because the will be always a $B$ after an $A$. in the other words for me, $(A+B)$ accepts $A…AB$ strings. so the question is trivially wrong and doesn't need to be asked.
But as I can see, the questioner and answerers don't think like that. So the definition of + notation must be different for us.
I'm here to ask what does it mean here if I'm wrong? thanks in advance.
Best Answer
Here the operator $+$ means alternation. It does not mean repeating the previous symbol one or more times. So, $(A+B)^{*}$ means: zero or more occurrences of $A+B$, which means zero or more occurrences of either $A$ or $B$.
Valid strings are: $\varepsilon,A,AA,AAA,B,BB,BBB,ABBA,BABA,\ldots$
We observe $(A+B)^*$ produces the same words as $(A^{*}B^{*})^*$.