GATE CS 2014 Set 2 Q15 — Regular and Context-free Languages

Let us analyze the two given statements:

Given languages:

• $L_1 = \{a^n \mid n \geq 0\} = a^*$
• $L_2 = \{b^n \mid n \geq 0\} = b^*$

Statement I: $L_1.L_2$ is a regular language

The concatenation of $L_1$ and $L_2$ is defined as:

Since $a^*b^*$ can be represented by a regular expression, it is a regular language. Alternatively, because regular languages are closed under concatenation, and both $L_1$ and $L_2$ are regular, their concatenation $L_1.L_2$ must also be regular. Therefore, Statement I is CORRECT.

Statement II: $L_1.L_2 = \{a^n b^n \mid n \geq 0\}$

In the concatenation $L_1.L_2$, the powers of $a$ and $b$ are chosen independently. That is, $L_1.L_2 = \{a^p b^q \mid p, q \geq 0\}$.

On the other hand, the language $\{a^n b^n \mid n \geq 0\}$ requires the number of $a$'s and $b$'s to be strictly equal.

• For example, the string $a^1 b^2 \in L_1.L_2$ (since $a^1 \in L_1$ and $b^2 \in L_2$).
• However, $a^1 b^2 \notin \{a^n b^n \mid n \geq 0\}$.

Thus, $L_1.L_2 \neq \{a^n b^n \mid n \geq 0\}$. Therefore, Statement II is INCORRECT.

Hence, only Statement I is correct.