GATE CS 2007 Q31 — Regular and Context-free Languages

To determine which language is regular, let us analyze each option:

• Option A: $L_1 = \{ww^R \mid w \in \{0, 1\}^+\}$ is the set of even-length palindromes. It requires a stack to match the symbols of $w$ with $w^R$ in reverse order, making it context-free but not regular.
• Option B: $L_2 = \{ww^Rx \mid x, w \in \{0, 1\}^+\}$ requires matching an arbitrary prefix $ww^R$ followed by $x$. Since the boundary between $ww^R$ and $x$ is not fixed and $ww^R$ requires memory, this language is not regular.
• Option C: $L_3 = \{wxw^R \mid x, w \in \{0, 1\}^+\}$. Let us simplify this expression:
  • Since $w \in \{0, 1\}^+$, its first symbol must be some $a \in \{0, 1\}$. We can write $w = a y$ for some $y \in \{0, 1\}^*$.
  • Then, $w^R = y^R a$.
  • Substituting these into the expression gives: $$wxw^R = (ay) x (y^R a) = a (y x y^R) a$$
  • Since $x \in \{0, 1\}^+$ (length $\ge 1$), the middle portion $z = y x y^R$ is also a non-empty string in $\{0, 1\}^+$.
  • Thus, any string in $L_3$ simply starts and ends with the same symbol ($0$ or $1$) and has a non-empty middle part (total length $\ge 3$).
  This can be represented by the regular expression: $$0(0+1)^+0 + 1(0+1)^+1$$ Since we can write a regular expression for $L_3$, it is regular.
• Option D: $L_4 = \{xww^R \mid x, w \in \{0, 1\}^+\}$ is not regular for the same reason as Option B, as it requires matching a suffix of the form $ww^R$.