\(\textbf{AB}\)-words are “words” formed from the letters \(\textbf{A}\) and \(\textbf{B}\) according to certain rules. The rules are applied starting with the empty word, containing no letters. The basic rules are:
If the current word is \(x\), then it can be replaced with the word that starts with \(\textbf{A}\), followed by \(x\) and ending with \(\textbf{B}\), written \(\textbf{A} x\textbf{B}\).
If the current word ends with \(\textbf{B}\), the final \(\textbf{B}\) can be removed.
Show how the word \(\textbf{AAAB}\) can be produced.
Describe precisely all the words that can be produced with these two rules. Justify your answer. You might like to write \(\textbf{A}^i\) for the word containing just \(i\) consecutive copies of \(\textbf{A}\), and similarly for \(\textbf{B}\); for example \(\textbf{A}^3 \textbf{B}^2 = \textbf{AAABB}\).
We now add a third rule:
- Reverse the word, and replace every \(\textbf{A}\) by \(\textbf{B}\), and every \(\textbf{B}\) by \(\textbf{A}\).
For example, applying this rule to \(\textbf{AAAB}\) would give \(\textbf{ABBB}\).
- Describe precisely all the words that can be produced with these three rules. Justify your answer.
Finally, we add a fourth rule.
- Reverse the word.
- Show that every word consisting of \(\textbf{A}\)s and \(\textbf{B}\)s can be formed using these four rules. Hint: show how, if we have produced the word \(w\), we can produce (a) the word \(\textbf{A}w\), and (b) the word \(\textbf{B}w\); hence deduce the result.
