Given the language \(L = \{ab, aa, baa\}\), which of the following strings are…
2012
Given the language \(L = \{ab, aa, baa\}\), which of the following strings are in \(L^*\)?
(1) abaabaaabaa
(2) aaaabaaaa
(3) baaaaabaaaab
(4) baaaaabaa
- A.
1, 2 and 3
- B.
2, 3 and 4
- C.
1, 2 and 4
- D.
1, 3 and 4
Attempted by 393 students.
Show answer & explanation
Correct answer: C
Key idea: A string is in L* exactly when it can be written as a concatenation of the words ab, aa, and baa.
String 1 (abaabaaabaa) = ab · aa · baa · ab · aa
String 2 (aaaabaaaa) = aa · aa · baa · aa
String 4 (baaaaabaa) = baa · aa · ab · aa
String 3 (baaaaabaaaab) is not in L*: it must begin with 'baa' (the only token starting with 'b'), and the remaining suffix cannot be fully decomposed into 'ab', 'aa', or 'baa', so no valid concatenation exists.
A video solution is available for this question — log in and enroll to watch it.