1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ In “xZy”, what is Z? $\endgroup$
    – MJD
    Nov 30, 2014 at 14:39
  • $\begingroup$ Z is a letter\sign that is not part of the sigma L is built on $\endgroup$
    – ron
    Nov 30, 2014 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, 2014 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, 2014 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, 2014 at 14:59

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 15:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .