## prove (a+b)*=a*(ba*)* [closed]

formal language and automata theory

regular expessions (a+b)* =a*(ba*)*

-
Welcome to MO! Please read FAQs and 'how to ask' to see how to phrase a question that would be appreciated here. Your question is difficult to understand; perhaps somebody can infer what the symbols ought to mean but still it would be nicer to have it spelled out so that more people can appreciate your question. – quid Nov 10 at 11:48
Quid, the question has completely standard notation. (See en.wikipedia.org/wiki/Regular_expression). But nevertheless, the expression in the title is different from the expression in the question itself, because of some misplaced asterisks. – Joel David Hamkins Nov 10 at 12:13
@Joel David Hamkins: right, so replace 'perhaps somebody can infer' by 'while some will know'. I think I still maintain the rest of my comment. – quid Nov 10 at 12:24

## closed as too localized by Michael Renardy, quid, Simon Thomas, Asaf Karagila, Brendan McKayNov 10 at 12:35

Your title expression $(a+b)^\ast=a^\ast(ba^\ast)^\ast$ is not true, since the right side allows the instance $b$ alone, but every nonempty instance on the left must have at least one $a$.

Meanwhile, the expression in the body of your question $(a+b)=a(ba^\ast)^\ast$ is not true, since all instances of the left expression have only one $b$, but on the right, we can have $abbbb$.

-
Joel, it seems the notation might not be as standard as you and I thought. To me, the LHS in the title, $(a+b)^*$, means the set of those sequences obtained by concatenating any number of sequences, each of which is either just $a$ or just $b$. In other words, it's the set of all words on the alphabet $\{a,b\}$, and these need not contain any $a$. So, on my understanding of the notation, the title formula is correct. – Andreas Blass Nov 10 at 13:50
Apparently Wikipedia uses | to mean what I would write as $+$. – Andreas Blass Nov 10 at 13:52
I haven't seen $+$ used to mean $\mid$, but I have seen it appearing as an exponent, as in $(a^+b)^\ast$. – Joel David Hamkins Nov 10 at 14:04
Joel, I've also seen it used as an exponent, with the meaning of "concatenate any non-zero number of copies". – Andreas Blass Nov 10 at 14:30
@Joel, many computer scientists use + for union because the set of regular languages is a semiring with union as addition. The $+$ is also used in exponents to indicate that the subsemigroup is to be generated instead of the submonoid (for which * uses). – Benjamin Steinberg Nov 11 at 1:01