Question 42

Analysis of $L_1 = \{w x y x \mid w, x, y \in (0 + 1)^+\}$:

• Notice that $x$ is non-empty ($|x| \ge 1$). In particular, $x$ can be chosen to be a single symbol: $x = 0$ or $x = 1$.
• If $x = 0$: the pattern becomes $w 0 y 0$, where $w, y \in (0+1)^+$.
• If $x = 1$: the pattern becomes $w 1 y 1$, where $w, y \in (0+1)^+$.
• Any string that matches $w x y x$ with $|x| > 1$ also matches either $w' 0 y' 0$ or $w' 1 y' 1$ by taking the first and last bits of $x$.
• Thus, $L_1 = (0+1)^+ 0 (0+1)^+ 0 \;\cup\; (0+1)^+ 1 (0+1)^+ 1$.
• Since $L_1$ can be expressed by a regular expression, $L_1$ is regular.

Analysis of $L_2 = \{x y \mid x, y \in (a + b)^*, |x| = |y|, x \ne y\}$:

• $L_2$ contains even-length strings where the first half $x$ differs from the second half $y$ in at least one position $i$.
• That is, for some $k$, the string has the form $u a v \cdot u' b v'$ or $u b v \cdot u' a v'$ with $|u| = |u'|$ and $|v| = |v'|$.
• This language can be generated by the following context-free grammar:
  $$S \to A B \mid B A$$
  $$A \to C A C \mid a$$
  $$B \to C B C \mid b$$
  $$C \to a \mid b$$
• Here $A$ generates strings where the middle character is $a$, and $B$ generates strings where the middle character is $b$. $A B$ produces an even-length string whose first half has $a$ at the same relative position where the second half has $b$.
• Thus, $L_2$ is context-free (though non-deterministic).

Therefore, $L_1$ is regular and $L_2$ is context-free.