1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Apr 12 '15 at 15:17
  • $\begingroup$ Also, what is $x$ in your specification of $L'$? $\endgroup$ – Henning Makholm Apr 12 '15 at 15:19
  • $\begingroup$ I edited according to your expactations $\endgroup$ – user220688 Apr 12 '15 at 15:31
  • $\begingroup$ 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. $\endgroup$ – wece Apr 21 '15 at 14:50

Your Answer

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

Browse other questions tagged or ask your own question.