1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Pål GD Feb 4 at 6:59
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Feb 4 at 10:56
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Feb 4 at 12:27
  • 1
    $\begingroup$ Put "middle third" in the search box on top of the page and you will find a hint by Yuval. $\endgroup$ – Hendrik Jan Feb 4 at 13:20
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Alternatively, you would try to create an algorithm that constructs a FSM for L' given a FSM for L, if you fail to produce a counter example. I must say I'd find both difficult at the moment. $\endgroup$ – gnasher729 Feb 4 at 12:25

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