TIFR CSE 2021 | Part B | Question: 5

Question

For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the following sentences.

1. $\overline{L}$ and $L^{\ast}$ are both context-free.
2. $\overline{L}$ is not context-free but $L^{\ast}$ is context-free.
3. $\overline{L}$ is context-free but $L^{\ast}$ is regular.

Which of the above sentence(s) is/are true if $L=\left \{ a^{n}b^{n} \mid n\geq 0\right \}$?

• A. Both (i) and (iii)
• B. Only (i)
• C. Only (iii)
• D. Only (ii)
• E. None of the above

Answer 1

Option $(B)$

$\bar{L} = \{a^nb^m|n \neq m ;n,m \geq 0\}$ This is CFL

$L^{*} = (a^nb^n)^*$ will always be CFL as CFL are closed under kleene-closure but it is not regular as it requires $b$ to match with the $a$ before starting with another runs of $a$.

Comments

Good question.