Let L = {ab, aa, baa}. Which of the following strings are not in L*.

Solution: We check each given string for membership in L*, where L = {ab, aa, baa}.

• abaabaaabaa: This string is in L*. One valid decomposition is ab · aa · baa · ab · aa.

• aaaabaaaa: This string is in L*. A valid decomposition is aa · aa · baa · aa.

• baaaaabaaaab: This string is not in L*. Proof by parsing from the end:

  1. Only the word 'ab' ends with the letter 'b', so the final two letters 'ab' must form the last token. Remove that 'ab'.

  2. The remaining suffix now ends with 'aa', so the preceding token must be 'aa' (the three-letter word 'baa' would require the last three letters to be 'baa', which they are not). Remove that 'aa'.

  3. After these removals the remaining prefix ends with 'ba' and its last three letters are 'aba'. Neither 'aa' nor 'baa' matches these ending letters, so no valid final token exists for the prefix. This contradiction means no full decomposition into words from L is possible.

• baaaaabaa: This string is in L*. One valid decomposition is baa · aa · ab · aa.

Conclusion: Among the four given strings, only baaaaabaaaab cannot be written as a concatenation of words from L, so it is not in L*.