GATE CS 2015 Set 2 Q51 — Regular and Context-free Languages

To determine which of the languages are regular, we analyze each one individually:

• Language $L_1$: We are given $L_1 = \{ wxw^R \mid w, x \in \{a, b\}^* \text{ and } |w|, |x| > 0 \}$.
  Let the first symbol of $w$ be $c \in \{a, b\}$, so $w = c u$ for some string $u$. Then $w^R = u^R c$.
  Substituting this, any string in $L_1$ can be written as: $$wxw^R = (cu) x (u^R c) = c (uxu^R) c$$ Since $|x| > 0$, the middle portion $x' = uxu^R$ also has length $|x'| \ge 1$.
  Thus, $L_1$ is simply the set of all strings of length $\ge 3$ that start and end with the same symbol. This can be defined by the regular expression: $$a(a+b)^+a + b(a+b)^+b$$ Since we can write a regular expression for $L_1$, $L_1$ is regular.
• Language $L_2$: $L_2 = \{ a^nb^m \mid m \neq n \text{ and } m, n \ge 0 \}$.
  This language requires comparing the count of $a$'s and $b$'s to ensure they are unequal. Since a finite automaton has finite memory, it cannot keep track of arbitrary counts. Thus, $L_2$ is not regular (it is a deterministic context-free language).
• Language $L_3$: $L_3 = \{ a^pb^qc^r \mid p, q, r \ge 0 \}$.
  This language consists of any number of $a$'s followed by any number of $b$'s followed by any number of $c$'s. It can be represented by the regular expression: $$a^*b^*c^*$$ Thus, $L_3$ is regular.

Therefore, only $L_1$ and $L_3$ are regular languages.