Consider \(L = \{a b, a a, b a a\}\) Which of the following string is NOT in…
2022
Consider \(L = \{a b, a a, b a a\}\)
Which of the following string is NOT in \( L^∗\) ?
- A.
baaaaabaaaaa
- B.
abaabaaabaa
- C.
aaaabaaaa
- D.
baaaabaa
Attempted by 363 students.
Show answer & explanation
Correct answer: A
Answer: baaaaabaaaaa is NOT in L*.
Reason: We use the fact that the words in L are 'ab' (length 2), 'aa' (length 2), and 'baa' (length 3).
Observation: any token that begins with 'b' must be 'baa'. Tokens that begin with 'a' have length 2.
For baaaaabaaaaa: it starts with 'b', so the first token must be 'baa' (consumes 3 characters). The remainder then has length 9 and starts with 'a'. Because the remaining tokens that start with 'a' all have length 2, the remainder would need to be a sum of even lengths, but 9 is odd. Thus this string cannot be written as a concatenation of words from L.
For abaabaaabaa: a valid decomposition is ab · aa · baa · ab · aa, so it is in L*.
For aaaabaaaa: a valid decomposition is aa · aa · baa · aa, so it is in L*.
For baaaabaa: a valid decomposition is baa · aa · baa, so it is in L*.