Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2012
Hard
Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
- A1, 2 and 3
- B2, 3 and 4
- 1, 2 and 4
- D1, 3 and 4
Explanation
L* consists of all strings formed by concatenating zero or more of {ab, aa, baa}. String 1, abaabaaabaa, decomposes as ab·aa·baa·ab·aa — valid. String 2, aaaabaaaa, decomposes as aa·aa·baa·aa — valid. String 4, baaaaabaa, decomposes as baa·aa·ab·aa — valid. String 3, baaaaabaaaab, cannot be fully decomposed into these three blocks without a leftover/mismatched symbol, so it is not in L*. Hence strings 1, 2 and 4 are in L*.
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.