# Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it.
$L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$
Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$
For language $L':$ $M'=(Q', \Sigma, \delta', q_{start}, F')$
$Q'=(Q\times Q\times Q\times Q\times Q) \cup \{q_{start}\}$
$\delta'((q_1,q_2, q_2,q_3,q_3), a\in \Sigma) = \{((\delta(q_1,a), \delta(q_2,b), q_2,\delta(q_3,c),q_3)\}$ for some $b,c\in\Sigma$ (automaton guesses)
$\delta'(q_{start},\epsilon)=\{(q_0,q_2, q_2,q_3, q_3)|q_2,q_3\in Q\}$
$F=\{(q_1,q_2,q_3,q_4,q_5)|q_5\in F\wedge q_1=q_3\wedge q_2=q_4\}$

Description in words
I guess three states (first of them is starting state in automaton for $L$). And first state advance according to characters on input. Second and third state advances also (but guessing character).
But I have five elemnents - two others are memory - it contains second and third state that we guessed. This memory is crucial for settling accepting states. To sum up:

$(q_1,q_2,q_3,q_4,q_5)$. $q_3$ contatins state that we guessed it for $q_2$ (it doesn't change during processing). Analogically, $q_5$ remember start state for $q_4$.

• You desperately need some actual sentences in words that describe what you're doing and why you think it works. Just a bunch of equations is (almost) never a complete solution of anything. – Henning Makholm Apr 12 '15 at 15:17
• Also, what is $x$ in your specification of $L'$? – Henning Makholm Apr 12 '15 at 15:19
• I edited according to your expactations – user220688 Apr 12 '15 at 15:31
• seems ok to me accept that you need do recognize $y$ (the word in the middle) and as it is done her you recognize $x$ the first word. – wece Apr 21 '15 at 14:50