Strings are known to not satisfy the commutative property. pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct


1 Answer 1


Simple solution: $a\cdot aa = aa \cdot a$?

In general there is a characterization due to Lyndon and Schützenberger. For nonempty words $x,y\in \Sigma^+$ the following are equivalent:

  • $xy=yx$
  • there exists $z\in \Sigma^+$ such that $x=z^k$ and $y=z^\ell$ for some $k,\ell >0$.
  • there exist $i,j>0$ such that $x^i = y^j$.

This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.

  • $\begingroup$ Oh yeah. I didn't think about it. It was actually simple :| Thanks for the response though $\endgroup$
    – Shannu
    Sep 1, 2017 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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