GATE CS 2020 Q8 — Regular and Context-free Languages

We analyze the two statements individually:

Statement I: If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular.

This statement is FALSE. We can show this using a counterexample:

• Let $L_1 = \{a^n b^n \mid n \ge 0\}$, which is a well-known non-regular language.
• Let $L_2 = \Sigma^* \setminus L_1$, which is also non-regular (since the complement of a regular language is regular, if $L_2$ were regular, $L_1$ would have to be regular).
• Their union is $L_1 \cup L_2 = \Sigma^*$, which is a regular language.

Since $L_1 \cup L_2$ is regular but neither $L_1$ nor $L_2$ is regular, Statement I does not hold.

Statement II: The class of regular languages is closed under infinite union.

This statement is FALSE. Regular languages are closed under finite union, but not necessarily under infinite union. We can show this using a counterexample:

• Let $\Sigma = \{a\}$. For each $i \ge 0$, define the language $L_i = \{a^{i^2}\}$.
• Each $L_i$ contains exactly one string, making it a finite language, and therefore regular.
• The infinite union of these languages is: $$L = \bigcup_{i=0}^{\infty} L_i = \{a^0, a^1, a^4, a^9, a^{16}, \dots\} = \{a^{i^2} \mid i \ge 0\}$$
• The language $L$ is not regular (which can be proven using the pumping lemma, as the spacing between consecutive string lengths increases monotonically).

Since the infinite union of regular languages can result in a non-regular language, Statement II does not hold.

Thus, both Statement I and Statement II are false.