GATE CS 2008 Q53 — Regular and Context-free Languages

To determine which of the given sets are regular, we analyze each language individually:

1. $L_1 = \{a^n b^{2m} \mid n \geq 0, m \geq 0\}$

   In this language, the number of $a$'s ($n$) and the number of $b$'s ($2m$) are completely independent.

   • $a^n$ for $n \geq 0$ can be generated by the regular expression $a^*$.
   • $b^{2m}$ for $m \geq 0$ represents an even number of $b$'s, which can be generated by $(bb)^*$.

   Since the two parts are independent, we can concatenate them to get the regular expression: $a^*(bb)^*$. Thus, $L_1$ is regular.

2. $L_2 = \{a^n b^m \mid n = 2m\}$

   This language requires the number of $a$'s to be exactly twice the number of $b$'s. Since a finite automaton has finite memory, it cannot keep track of an arbitrary count to enforce this dependency. Thus, $L_2$ is not regular (it is deterministic context-free).

3. $L_3 = \{a^n b^m \mid n \neq m\}$

   This language requires comparing the count of $a$'s and $b$'s to ensure they are unequal. Since a finite automaton cannot perform arbitrary counting and comparison, $L_3$ is not regular (it is context-free).

4. $L_4 = \{xcy \mid x, y \in \{a, b\}^*\}$

   Here, $x$ and $y$ can be any arbitrary strings over the alphabet $\{a, b\}$, separated by a single character $c$. This can be directly represented by the regular expression: $$(a+b)^* c (a+b)^*$$ Since it can be described by a regular expression, $L_4$ is regular.

Therefore, only I and IV are regular sets.