-1
$\begingroup$

formal language and automata theory

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

$\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$
    – user9072
    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$ 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$
    – user9072
    Nov 10, 2012 at 12:24

1 Answer 1

2
$\begingroup$

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

$\endgroup$
15
  • 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$ Nov 10, 2012 at 13:50
  • $\begingroup$ Apparently Wikipedia uses | to mean what I would write as $+$. $\endgroup$ 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$ 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$ 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$ Nov 11, 2012 at 1:01

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