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.
Conditions for: $xy=zw$ and $yx=wz$
-
0Obviously, it is sufficient that $x=z$ and $y=w$. – 2012-07-05
1 Answers
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}$.