Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Could someone please guide me how to go about solving this problem?

$$ baa \in a^*b^*a^*b^* .$$

The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any combination of $a$'s or $b$'s).

Intuitively, I would say yes of course it's an element, but how can I show it more formally?

"*" denotes Kleene Star.

share|cite|improve this question
There is a mild technicality, in that formally the Kleene star operation applies to sets. So it really should be $\{a\}^\ast\{b\}^\ast \{a\}^\ast \{b\}^\ast$. But $a^\ast b^\ast a^\ast b^\ast$ is often used as an (improper) abbreviation. So unless your instructor has made a big point of formal correctness, the answers already given are perfectly good. – André Nicolas Sep 20 '11 at 4:13
up vote 5 down vote accepted

Be careful. a*b*a*b* is not the set of "all combinations of a's and b's". For instance, baba is not in this set.

Remember that * means "zero or more". So the elements of a*b*a*b* are of the form:

  • some number of a (possibly zero), followed by
  • some number of b (possibly zero), followed by
  • some number of a (possibly zero), followed by
  • some number of b (possibly zero).

To show baa is of this form, it's enough to say how many of each letter you are using at each step. For instance, aba is in the set, because it consists of 1 a, 1 b, 1 a, 0 b. How would you do this for baa?

share|cite|improve this answer
Thank you, that totally makes sense now. – Blue Pony Inc. Sep 20 '11 at 3:01

Ya. Its true. * means the element can be any non-negative integer(including zero). Consider... $$a^0b^1a^2b^0$$ which gives baa.

share|cite|improve this answer

To show "more formally", just indicate how many of the first a's from "a*b*a*b*" you want to generate. Then do the same for the first b. Then second a and second b. The rule is you can take zero or more of each, but you have to respect order (you can't mix them).

share|cite|improve this answer

$a^* b^* a^* b^* = \{ a^m b^n a^p b^q : m,n,p,q\in \mathbb N \} $. (My $\mathbb N$ contains $0$.) Then $baa= a^0 b^1 a^2 b^0$.

share|cite|improve this answer

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.