Take the 2-minute tour ×
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.

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|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
add comment

4 Answers 4

up vote 4 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|improve this answer
    
Thank you, that totally makes sense now. –  Blue Pony Inc. Sep 20 '11 at 3:01
add comment

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

share|improve this answer
add comment

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|improve this answer
add comment

$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|improve this answer
add comment

Your Answer

 
discard

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.