Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

formal language and automata theory

regular expessions (a+b)* =a*(ba*)*
please answer I want the proof thank you

share|improve this question

closed as too localized by Michael Renardy, quid, Simon Thomas, Asaf Karagila, Brendan McKay Nov 10 '12 at 12:35

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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 '12 at 11:48
3  
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 '12 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 '12 at 12:24

1 Answer 1

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$.

share|improve this answer
2  
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 '12 at 13:50
    
Apparently Wikipedia uses | to mean what I would write as $+$. –  Andreas Blass Nov 10 '12 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 '12 at 14:04
1  
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 '12 at 14:30
2  
@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 '12 at 1:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.