Is word substitution invertible? Here is the problem. Let us say we have a word made up of two letters, for example, $ABBBA$. Say I enforce the substitution $A\to AB$ to get the word $ABBBBAB$. Is it always the case that if I know the final word and the substitution, I can blindly turn $AB\to A$ one by one from left to right and get the original word? Clearly, you can create the substitution word "accidentally":
For example:
$ABA$ enforce $A\to ABA$ then we get $ABABABA$, notice here we created another $ABA$, doing reverse substitution still works though. The issue is, what if we create the substitution word in the beginning? Then I think we will not go back to the original. I do not think that is possible, but was wondering if anyone could confirm my suspicion.
 A: Let $A = \{a, b\}$ and let $u, v \in A^*$. A well-known result (see for instance [1, Chapter 1]) states that the following conditions are equivalent:

*

*the monoid generated by $u$ and $v$ is not free,

*$uv = vu$,

*$u = w^p$ and $v = w^q$ for some $w \in A^*$ and some $p, q \geqslant 0$.

It follows that the monoid morphism $f: A^* \to A^*$ defined by $f(a) = u$ and $f(b) = v$ is injective if and only if $uv \not= vu$.
EDIT. For instance, if $f(a) = ab$ and $f(b) = b$, then $f$ is injective since $(ab)a = aba \not= aab = a(ab)$. If $f(a) = b^n$ and $f(b) = b$, then $f$ is not injective since $b^nb = bb^n$ (or directly since $f(a) = f(b^n)$.
[1] Lothaire, M. Combinatorics on words. Corrected reprint of the 1983 original, with a new preface by Perrin. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. xviii +238 pp. ISBN: 0-521-59924-5
A: This particular substitution,  $A \mapsto AB, B \mapsto B$, does appear to be invertible.  To see this, consider the image of a word under the mapping.  It cannot end in $A$ since the mapping always ends in $B$.  If The last two letters are $AB$ the $A$ component can only have come from operation of $A \mapsto AB$ and so the two last letters together invert to $A$.  If it ends in $BB$, the last $B$ must have originated from a $B$ in the original word.
You can now invert the last part of the word, removing either one or two letters and then repeat.  Thus the substitution is one to one and invertible.
In fact, I conjecture that as long as the $A$ mapping is not aa repetition of the $B$ mapping and vice versa such a map should always be invertible.  You might want to try to prove that.
