GATE CS 1992 Q16 — Regular and Context-free Languages

Statements (i) and (ii) are true, while statement (iii) is false.

1. The union of two recursive languages is recursive (True):
   If $L_1$ and $L_2$ are recursive languages, there exist Turing machines $M_1$ and $M_2$ that decide them (i.e., they always halt and either accept or reject). We can construct a decider $M$ for $L_1 \cup L_2$ as follows: on input $w$, run $M_1$ on $w$. If $M_1$ accepts, accept. If $M_1$ rejects, run $M_2$ on $w$. If $M_2$ accepts, accept; otherwise, reject. Since both $M_1$ and $M_2$ are guaranteed to halt, $M$ always halts and decides $L_1 \cup L_2$. Thus, recursive languages are closed under union.


2. The language $L = \{0^n \mid n \text{ is a prime}\}$ is not regular (True):
   Assume $L$ is regular. Let $p$ be the pumping length. Choose a prime $n \ge p + 2$. The string $w = 0^n \in L$. By the Pumping Lemma, $w = xyz$ such that $|xy| \le p$, $|y| = m \ge 1$, and $xy^k z \in L$ for all $k \ge 0$.
   The length of $xy^k z$ is given by $|xy^k z| = n + (k-1)m$.
   If we choose $k = n + 1$, the length becomes $n + nm = n(1+m)$. Since $n \ge 3$ and $m \ge 1$, both factors $n$ and $1+m$ are greater than or equal to $2$. Thus, $n(1+m)$ is composite, meaning $0^{n(1+m)} \notin L$, which contradicts the Pumping Lemma. Hence, $L$ is not regular.


3. Regular languages are closed under infinite union (False):
   Any single-string language $\{0^n\}$ is finite and therefore regular. However, the infinite union of such regular languages, $\bigcup_{n \text{ is prime}} \{0^n\}$, results in the non-regular language $\{0^n \mid n \text{ is prime}\}$. Thus, regular languages are not closed under infinite union.