GATE CS 2012 Q25 — Regular and Context-free Languages

To determine which strings belong to $L^*$, we check if they can be partitioned into a sequence of substrings from $L = \{ab, aa, baa\}$.

• String 1: $abaabaaabaa$
  Partition: $(ab) \cdot (aa) \cdot (baa) \cdot (ab) \cdot (aa)$
  Since all components are in $L$, this string is in $L^*$.
• String 2: $aaaabaaaa$
  Partition: $(aa) \cdot (aa) \cdot (baa) \cdot (aa)$
  Since all components are in $L$, this string is in $L^*$.
• String 3: $baaaaabaaaab$
  This string ends with $b$. Since $ab$ is the only element in $L$ ending with $b$, the string must end with the token $ab$, leaving the prefix $baaaaabaaa$ ($b a^5 b a^3$).
  Any block starting with $b$ must begin with $baa$ (the only element starting with $b$) followed by some number of $aa$ tokens, which always produces an even number of $a$'s ($b a^{2n+2}$). However, the first block has $5$ $a$'s ($b a^5$), which is odd and cannot be formed. Thus, this string is not in $L^*$.
• String 4: $baaaaabaa$
  Partition: $(baa) \cdot (aa) \cdot (ab) \cdot (aa)$
  Since all components are in $L$, this string is in $L^*$.

Therefore, strings 1, 2, and 4 are in $L^*$.