Conditions for: $xy=zw$ and $yx=wz$

Question

Let $x,y,z,w$ be finite strings. Find the necessary and sufficient conditions for the following two equations to hold simultaneously: $$xy=zw$$ and $$yx=wz$$ Automata Theory is new to me and i am struggling with this problem given in my tutorial sheet.Help me.Thanks in advance.

Answer 1

If x and z are of the same length, then x = z and y = w. Otherwise, without loss of generality, suppose that z is larger than x. Then let z = xa. In that case, from xy = zw, y = aw. Substituting these in yx = wz,

awx = wxa.

Call wx=b.

Then ab = ba.

Again, either a = b or let b = ac.

In that case, we get aac=aca, or ac = ca.

This process can be continued until we get some point where ad = da will mean a = d (so this part works a bit like euclid's algorithm).

In other words, a and b have a 'common factor', a string whose repetition yields both a and b. Let this be f. Let a = $f^p$ and b=wx be $f^q$. So our condition is that either x = z and y = w or z can be written as xa (the case where x is longer and thus x = za is just a renaming of the variables), where a and wx have a common factor f such that a can be written as $f^p$ for some p and wx can be written as $f^q$ for some q.

I have already shown this to be necessary. For sufficiency, let y = $f^pw$ and z = $xf^p$. Not xy = zw = $xf^pw$ and yx = wz = $f^{p+q}$.