0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.