The free idempotent monoid is the quotient object of the free monoid that identifies the lists up to idempotency. In laymen's terms, if the list has two or more contiguous sub-lists that compare equal, the sub-lists can be replaced by one sub-list, while retaining overall equivalence of the list.

The free idempotent monoid is the quotient object of the free monoid that identifies the lists up to idempotency. In lay terms, if the list has two or more contiguous sub-lists that compare equal, the sub-lists can be replaced by one sub-list, while retaining overall equivalence of the list.

If \$x\$ and \$y\$ both have length two, we are done. Otherwise, let \$\alpha''\$ be the third character in \$x\$, and let \$\beta''\$ be the third character in \$y\$. It's obvious that the strings \$\alpha\alpha'\alpha''\$ and \$\beta\beta'\beta''\$ are irreducible. Now, every member of the the class \$x\$ belongs has \$\alpha''\$ as the first character when the longest prefix being equivalent to the string \$\alpha\alpha'\$ is stripped off, and likewise for \$y\$ and \$\beta''\$, it follows that \$\alpha'' = \beta''\$.

If \$x\$ and \$y\$ both have length two, we are done. Otherwise, let \$\alpha''\$ be the third character in \$x\$, and let \$\beta''\$ be the third character in \$y\$. It's obvious that the strings \$\alpha \alpha' \alpha''\$ and \$\beta \beta' \beta''\$ are irreducible. Now, every member of the the class \$x\$ belongs has \$\alpha''\$ as the first character when the longest prefix being equivalent to the string \$\alpha\alpha'\$ is stripped off, and likewise for \$y\$ and \$\beta''\$, it follows that \$\alpha'' = \beta''\$.

Worked example

For suppose the inputted string is QUAQUAUAL. The substring QUA contiguously appears twice, enabling the input to be reduced to QUAUAL. Then again, it has the substring UA contiguously appearing twice, enabling the input to be reduced to QUAL. Then, we identify there is no substring contiguously appearing multiple times, resulting in outputting QUAL.