Question 18

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

• Consider the alphabet $\Sigma = \{a\}$.
• Let $L_1 = \{a^p \mid p \text{ is prime}\}$, which is known to be non-regular.
• Let $L_2 = \Sigma^* \setminus L_1 = \{a^k \mid k \text{ is composite or } 0, 1\}$, which is also non-regular.
• Their union is $L_1 \cup L_2 = \Sigma^* = a^*$, which is clearly regular.
• Thus, the union of two non-regular languages can be regular. Statement I is FALSE.

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

• Any arbitrary language $L \subseteq \Sigma^*$ can be expressed as the infinite union of singleton string languages: $L = \bigcup_{w \in L} \{w\}$.
• Every singleton language $\{w\}$ is finite and therefore regular.
• If regular languages were closed under infinite union, every language (including non-regular and undecidable languages like the Halting Problem) would be regular, which is impossible.
• Thus, regular languages are not closed under infinite union. Statement II is FALSE.

Since both statements are false, the correct option is 'Neither I nor II'.