2
$\begingroup$

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.

  • 0
    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.2011-09-20

4 Answers 4

5

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?

  • 0
    Thank you, that totally makes sense now.2011-09-20
1

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

1

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

1

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