Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

Question

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.

Answer 1

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?

Answer 2

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

Answer 3

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

Answer 4

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