I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle of it but I'm having difficulty with this one, assume L over Sigma is regular , prove that the language xZy is regular if given that yx belongs to L. (x is a suffix y is a preffix in L). Now, if the language to prove was yZx (keep in mind Z is a letter NOT in Sigma) then I could just take 2 copies of the given DFA of the regular L and connect each state in the first copy to a state in the second copy through a Delta(q1,Z) = q2 thus creating yZx from 2 yx automatons, the issue here is that the regular language is flipped I.E. xy is given and you need to prove yZx rather than xZy, I thought about trying to prove that if yx is regular then xy is regular and then use the new ragular language like I stated but I didn't manage that as well, the only almost possible soultion I found was using Cycle(L) – I thought about proving a cycle(L) to be regular (I know thats true) so that if I have L={ab,abb} I can prove cycle(L) is regular I.E L' = {ab,abb,ba,bab,bba} and then do intersection between L and L' so I will have only the words flipped but that does not give me XY from YX….
I've also tried using 2 copies of the DFA of L, and adding a state q(-1) connected through epsilons to all other states in the first one and a q(n+1) state on the second automaton connecting every state on the second automaton to it, then if I had the expression xy , I can start from y using the epsilon then moving through the Z to the second copy and then do X on the second copy and using epsilon to go to the finishing state…
It sounded good in my head but I couldnt write it formally and stumbled upon various issues trying to do so…
So, in conclusion. I'm lost. Any suggestion or even a hint as to how to construct this language will be appriciated…
Best Answer
Hint: Let $M_y$ be the automaton that recognizes suffixes from $L$ and $M_x$ be the automaton that recognizes prefixes from $L$. Neither automaton has any transitions on $Z$, since $Z\notin\Sigma$.
Could you connect $M_y$ to $M_x$ somehow, and let $M_y$ recognize the $y$ part of the input string, and $M_x$ recognize the $x$ part?