Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns very little results on this topic. I would be very grateful.

share|cite|improve this question
What is $(a\mid b)$? – JavaMan Feb 2 '12 at 3:41
@JavaMan: a, b or ab. Right? – hey Feb 2 '12 at 3:42
up vote 9 down vote accepted

Assuming that $|$ refers to an "or" selection (so the character can be either an $a$ or a $b$, then $(a|b)^*$ is all strings composed of the characters $a$ and/or $b$, including the empty string. On the other hand, $a^*b^*$ refers to all strings composed of the characters $a$ and/or $b$ which has all $a$'s preceding all $b$'s, again including the empty string.

For instance, $ababbbabab$ would be a member of $(a|b)^*$ but not $a^*b^*$, whereas $aaabbbbb$ would be a member of both.

share|cite|improve this answer
Could you please give me a few more examples, I would really be grateful. – hey Feb 2 '12 at 3:48
Unfortunately I don't know what kind of examples you want. If you do a search for Kleene star examples there are references all over the place. One in particular is The Regular Language section contains some good examples/patterns. – Kurtis Zimmerman Feb 2 '12 at 3:50
Thanks, those example will be enough, I think I almost got it now. – hey Feb 2 '12 at 4:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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