ISRO CS 2023 Q.59: solution and answer

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

1. Context-free languages (CFLs) are closed under union, concatenation and Kleene star, and under intersection with a regular language. They are not closed under intersection with each other or under complement.

2. Option (a): run a PDA for the CFL in parallel with a DFA for the regular language (product construction). The product machine is still a PDA, so the intersection is context-free. This statement is true.

3. Option (b): take $L_1=\{a^n{b}^n\mid n\ge 0\}$, which is context-free, and $L_2=a^{\ast }{b}^{\ast }$, which is regular. Then $L_1\cap L_2=\{a^n{b}^n\mid n\ge 0\}$, which is context-free but not regular. So the intersection need not be regular, and this statement is false.

4. Option (c): for grammars with start symbols $S_1,S_2$ (with disjoint variable sets), add a new start symbol $S$ with rules $S\to S_1\mid S_2$. This is a CFG for the union, so the statement is true.

5. Option (d): regular languages are closed under union (use an NFA with a new start state and $\epsilon$-moves to the two start states). This statement is true.

6. Only option (b) is false, so the answer is (b).