GATE CS 2020 Set 1 — Question 42

Analyze $L_1$:
$L_1 = \{wxyx \mid w, x, y \in (0+1)^+\}$.
Since $x \in (0+1)^+$, $x$ must end in either $0$ or $1$. Also, $x$ appears earlier in the string. Since $w, y \in (0+1)^+$, there is at least one character before the first $x$ and at least one character between the two occurrences of $x$.
Essentially, this language describes strings that end with a substring $x$ which has appeared before. If we take $x$ to be just the last character (either '0' or '1'), the condition simplifies to: the string ends in '0' and has a '0' somewhere before (separated by at least one char), OR the string ends in '1' and has a '1' somewhere before.
Regex: $\Sigma^+ 0 \Sigma^+ 0 \cup \Sigma^+ 1 \Sigma^+ 1$. This is a Regular Language.Analyze $L_2$:
$L_2 = \{xy \mid |x| = |y|, x \neq y\}$.
This is the set of even-length strings where the first half is not equal to the second half. The complement of this language (with respect to even-length strings) is $\{ww \mid w \in (a+b)^*\}$, which is known to be not Context-Free (CFL). However, the complement of a non-CFL can be CFL. The language $\{xy \mid |x|=|y|, x \neq y\}$ is a well-known Context-Free Language. It can be generated by a non-deterministic PDA that guesses the position where the two halves differ.
Since $L_2$ is CFL but its complement (relative to even strings) is not CFL (and thus not Regular), $L_2$ is CFL but not Regular.Conclusion: $L_1$ is Regular and $L_2$ is Context-Free.