# Automata Language regularity proof by construction.

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

• In “xZy”, what is Z? – MJD Nov 30 '14 at 14:39
• Z is a letter\sign that is not part of the sigma L is built on – ron Nov 30 '14 at 14:41
• And you're given only that $yx$ is in $L$, not that $y$ and $x$ are each in $L$, correct? If I have that right, then your idea of connecting two automatons for $L$ wasn't going to work anyway. – MJD Nov 30 '14 at 14:46
• I'm not given anything else , but how would you approach this then ? either proving or disproving – ron Nov 30 '14 at 14:55
• Do you already know that if $X$ is a regular language, then the set of all suffixes from $X$ is also a regular language? – MJD Nov 30 '14 at 14:59

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?
• No, that's wrong. An automaton with all its states accepting accepts every string, not just the set of prefixes of $L$. – MJD Nov 30 '14 at 15:10