GATE CS 2020 Q32 — Regular and Context-free Languages

To determine the classes of the given languages, we analyze $L_1$ and $L_2$ individually:

Analysis of $L_1$:

The language is defined as $L_1 = \{ wxyx \mid w,x,y \in (0+1)^{+} \}$. Let $x$ end with a single symbol $a \in \{0, 1\}$, so we can write $x = x'a$ where $x' \in (0+1)^*$. Substituting this back:

Let $w_1 = wx'$ and $y_1 = yx'$. Since $w, y \in (0+1)^+$, we must have $w_1, y_1 \in (0+1)^+$. Thus, any string in $L_1$ can be simplified to have a single-symbol matching marker at the end of each segment. This allows us to write $L_1$ as the union of two regular languages:

This corresponds to the regular expression $(0+1)^+ 0 (0+1)^+ 0 + (0+1)^+ 1 (0+1)^+ 1$. Hence, $L_1$ is regular.

Analysis of $L_2$:

$L_2 = \{xy \mid x,y \in (a+b)^{*}, |x|=|y|, x \neq y \}$ represents the set of even-length strings where the first half is not equal to the second half. This means there is at least one position $i$ where the symbol in the first half differs from the symbol in the second half.

We can generate $L_2$ using the following Context-Free Grammar (CFG):

Here, $A$ generates odd-length strings with $a$ in the middle, and $B$ generates odd-length strings with $b$ in the middle. The concatenation $AB$ ensures that the mismatch occurs at the exact corresponding index in both halves. Thus, $L_2$ is context-free (but not regular).