\(\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.