# How to prove a language isn't necessarily regular? [duplicate]

Assuming we have a regular language $$L$$, how can we prove that $$L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$$ isn't necessarily regular.

So far I can't come up with much for how to solve this. I was thinking we could solve this by either generating an example where $$L'$$ isn't regular or we could use the pumping-lemma, but I'm unsure how to get started. This was the hardest one in my set of practice problems.

• Yes, it sounds like The Pumping Lemma is the way to go. You have to look at a couple of examples where pumping lemma is used to figure out how to apply it. If you are stuck, feel free to elaborate on where you are stuck. – Pål GD Feb 4 at 6:59
• Even proving that xz is an element of L' might be difficult because I would have to find an y that I can insert in the middle to create an element of L, and that might be difficult to find. – gnasher729 Feb 4 at 10:56
• PS. I thought about it, and given a FSM for L, you can quite easily check whether w is an element of L' in O(n*m) where m is the number of states in L, and n is the length of w. – gnasher729 Feb 4 at 12:27
• Put "middle third" in the search box on top of the page and you will find a hint by Yuval. – Hendrik Jan Feb 4 at 13:20

If we take $$L = \{a^n \mid n \in \mathbb{N}\}$$, then $$L' = \{a^{2n} \mid n \in \mathbb{N}\}$$, which is a perfectly fine regular language. Or even more trival, we could observe that $$\emptyset' = \emptyset$$.
As such, it does not hold that $$L'$$ is never regular for a regular language $$L$$. This means that answering the question will involve constructing a particular language $$L$$ for which you can prove that $$L'$$ is not regular (and such a proof could use the pumping lemma).
As a heuristic for how to attempt this, I would first look at some typical examples of non-regular languages, and try to find a way to express them as $$L'$$ for some regular language. If I don't succeed with that, I'd attempt to built $$L$$ by simultaneously ensuring that $$L$$ itself is regular, and by running the pumping lemma on $$L'$$ to prove that it is not.