1
$\begingroup$

What's the difference between $a^*+b^*$ and $(a+b)^*$?

I was going through this question. So according to the question-:

(a+b)* generates $\in$, a,b,ab,ba,aa,ba,...

whereas a*+b* generates $\in$, a,aa,aaa,b,bb,bbb etc.

Why can't a*+b* generate ab? What's stopping it from generating it? I feel like I am missing something fundamental. (Even if I take english meaning of word "OR", (a+b)* should generate same as a,aa,b,bb etc.)

I don't understand what's going on here. Please help me.

$\endgroup$
1
  • 1
    $\begingroup$ Have you ever seen a definition of the language generated by a regular expression? $\endgroup$ Apr 17, 2022 at 9:41

1 Answer 1

2
$\begingroup$

If $E$ and $F$ are regular expressions then $E+F$ is also a regular expression that matches all words that are matched by at least one of $E$ and $F$.

In you case $E=a^*$, $F=b^*$, and $E+F=a^*+b^*$. The word $ab$ is not matched by $a^*+b^*$ since it is not matched by $a^*$ nor by $b^*$.

$\endgroup$
4
  • $\begingroup$ thank you. ok then how does (a+b)* accepts ab,ba etc? i mean a accepts a,aa,aaa...b accepts b,bb,bbb...a+b should accept a,b,aa,bb,aaa,bbb...then ?? $\endgroup$
    – bafgil
    Apr 17, 2022 at 9:52
  • $\begingroup$ a only matches $a$, b only matches $b$, a+b matches all and only the words in $\{ a, b\}$. (a+b)* matches any word consisting of the concatenation of any number (possibly $0$) of words in $\{ a, b\}$. $\endgroup$
    – Steven
    Apr 17, 2022 at 10:04
  • $\begingroup$ Thanks. so a matchs a,aa,aaa...b matches b,bb,bbb so a+b matches a,aa,aaa...,b,bb,bbb...hence (a+b)* matches the combinations of them. (I think my confusion lies in what closure does. I know what it does, but I don't know definition of it, like how it performs). $\endgroup$
    – bafgil
    Apr 17, 2022 at 10:36
  • $\begingroup$ No. a matches only $a$ (it does not match $aa$, $aaa$, $\dots$), and b matches only $b$. $\endgroup$
    – Steven
    Apr 17, 2022 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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