Consider L = {ab, aa, baa}. Which of the following strings is NOT in L*?

Concept

For a finite set of words L, the Kleene closure L* contains exactly the strings formed by concatenating zero or more complete words from L.

To test membership, scan from left to right and continue only with a word of L that matches the next characters; membership holds only when some complete scan consumes every character.

Application

1. For baaaaabaaaaa, the first character b forces the word baa, so the scan reaches position 3 and leaves aaabaaaaa.

2. From position 3, the next matching words are forced in sequence: aa reaches position 5, ab reaches position 7, aa reaches position 9, and aa reaches position 11. One final a remains, but L contains no one-character word, so the scan cannot reach position 12.

3. The string abaabaaabaa has the complete decomposition ab · aa · baa · ab · aa.

4. The string aaaabaaaa has the complete decomposition aa · aa · baa · aa.

5. The string baaaabaa has the complete decomposition baa · aa · baa.

Cross-check

The three complete decompositions consume their strings exactly. The scan of baaaaabaaaaa stops at position 11 of 12, which independently confirms the unmatched final character.

Therefore, baaaaabaaaaa is not in L*.