CLR cover
Previous problem

Problem 2: Simple Case of Codicity Testing

Next problem

A set $\{w_1,w_2,\dots,w_n\}$ of words drawn from an alphabet $A$ is a (uniquely decipherable) code if for every two sequences (noted as words) $i_1i_2\cdots i_k$ and $j_1j_2\cdots j_\ell$ of indices from $\{1,2,\dots,n\}$ we have $$i_1i_2\cdots i_k \neq j_1j_2\cdots j_\ell \;\Rightarrow \; w_{i_1}w_{i_2}\cdots w_{i_k} \neq w_{j_1}w_{j_2}\cdots w_{j_\ell}.$$ In other words, if we define the morphism $h$ from $\{1,2,\dots,n\}^*$ to $A^*$ by $h(i)=w_i$, for $i\in \{1,2,\dots,n\}$, the condition means that the morphism is injective.

For an arbitrary integer $n$ there is no known linear-time algorithm for testing the codicity property. However, the situation is extremely simple for $n=2$: it is enough to check if the two codewords commute, that is, if $w_1w_2 = w_2w_1$.

Show that $\{x,y\}$ is a code if and only if $xy \neq yx$.