If $L$ is regular, is $L' = \{xz \mid \exists y, y \in \Sigma^* \text{ such that } |x|=|y|=|z|\text{ and }xyz \in L\}$ regular?

Question

I know how that if the condition $|x|=|y|=|z|$ is relaxed, then we get another regular set, as is shown by the construction in this question or this one. But I am not able to solve for this case when the condition on lengths of $x,y,z$ is imposed.

Answer 1

The answer is no, and was first given in [1]. Here is a slightly modified version of their argument.

Let $L = a^*ba^*ba^*$ and let $'=\{ \mid \exists \in \{a,b\}^* \text{ such that } |x| = |y| = |z| \text{ and }xyz \in L\}$. Suppose that $L'$ is regular. Then so is its intersection with the regular language $a^*bba^*$. Now, if you want to remove the middle part of $a^iba^jba^k$ and get two consecutive $b$'s, you have to start with a word of the form $a^nba^{n+1}ba^n$. It follows that $L' \cap a^*bba^* = \{a^nbba^n \mid n \geqslant 0\}$ and I let you verify that this language is not regular.

[1] R. E. Stearns and J. Hartmanis, Regularity preserving modifications of regular expressions, Information and Control 6 (1963), 55–69.