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

  • $\begingroup$ In “xZy”, what is Z? $\endgroup$ – MJD Nov 30 '14 at 14:39
  • $\begingroup$ Z is a letter\sign that is not part of the sigma L is built on $\endgroup$ – ron Nov 30 '14 at 14:41
  • $\begingroup$ 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. $\endgroup$ – MJD Nov 30 '14 at 14:46
  • $\begingroup$ I'm not given anything else , but how would you approach this then ? either proving or disproving $\endgroup$ – ron Nov 30 '14 at 14:55
  • $\begingroup$ Do you already know that if $X$ is a regular language, then the set of all suffixes from $X$ is also a regular language? $\endgroup$ – 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?

  • $\begingroup$ this is exactly what I was going for when I said taking 2 copies, and I'll explain further, if you look at the automaton recognizes all the prefixes from L thats just the automaton of L with all of its states accepting, same goes for the suffixes hence you actually get 2 copies of the original automaton, am I wrong ? $\endgroup$ – ron Nov 30 '14 at 15:09
  • $\begingroup$ No, that's wrong. An automaton with all its states accepting accepts every string, not just the set of prefixes of $L$. $\endgroup$ – MJD Nov 30 '14 at 15:10
  • $\begingroup$ I see your point now, let me dwell on that for a while :) thank you very much. $\endgroup$ – ron Nov 30 '14 at 15:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.