formal language and automata theory
regular expessions
(a+b)* =a*(ba*)*
please answer
I want the proof
thank you
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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. $\endgroup$– user9072Commented Nov 10, 2012 at 11:48
-
3$\begingroup$ 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. $\endgroup$– Joel David HamkinsCommented Nov 10, 2012 at 12:13
-
$\begingroup$ @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. $\endgroup$– user9072Commented Nov 10, 2012 at 12:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
15
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$.
answered Nov 10, 2012 at 12:18
-
2$\begingroup$ 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. $\endgroup$ Commented Nov 10, 2012 at 13:50 -
$\begingroup$ Apparently Wikipedia uses | to mean what I would write as $+$. $\endgroup$ Commented Nov 10, 2012 at 13:52
-
$\begingroup$ I haven't seen $+$ used to mean $\mid$, but I have seen it appearing as an exponent, as in $(a^+b)^\ast$. $\endgroup$ Commented Nov 10, 2012 at 14:04
-
1$\begingroup$ Joel, I've also seen it used as an exponent, with the meaning of "concatenate any non-zero number of copies". $\endgroup$ Commented Nov 10, 2012 at 14:30
-
2$\begingroup$ @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). $\endgroup$ Commented Nov 11, 2012 at 1:01