Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?

Question

I recently found a question asking whether the language given below is context-free or not:

$L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$

My intuition is that I can design a non-deterministic push-down automaton for the language. I would appreciate if you could correct me if I am wrong, or brief me on how I could prove that it is indeed context-free.

Answer 1

It’s a trick question. There must be four letters or more. Let the last letter be a, where a is 0 or 1. If any other letter other than the first or second to last is a, then the string is in L. (Pick x = a, w = everything before the first a, y = everything between first and last a). If you can’t find a in these places, the string cannot be in the language because you can’t match the last x with another one.

So you don’t have to check for two equal strings of identical length at all, the language is much simpler. And it is regular.