\(\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.
Apply Rule (1) three times to get \(\textbf{AAABBB}\), and then apply Rule (2) twice to give \(\textbf{AAAB}\).
- 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}\).
Applying Rule (1) \(i\) times will produce the word \(\textbf{A}^i \textbf{B}^i\). We can then remove any number of the \(\textbf{B}\)s by applying Rule (2). These two rules cannot produce any word containing a \(\textbf{B}\) before an \(\textbf{A}\).
So we can produce any word of the form \(\textbf{A}^i \textbf{B}^j\) where \(i \ge j \ge 0\).
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.
Rule (3) still keeps all the \(\textbf{A}\)s before all the \(\textbf{B}\)s. But now we can produce any word of the form \(\textbf{A}^i \textbf{B}^j\) with \(i \ge 0\) and \(j \ge 0\).
For \(i \ge j\), apply the rules exactly as in (ii) above. For \(j>i\), apply Rule (1) \(j\) times and Rule (2) \(j-i\) times, and then apply Rule (3) once.
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.
By first applying Rule (1) to \(w\) we get \(\textbf{A} w \textbf{B}\), and then applying Rule (2) we get \(\textbf{A}w\).
Let \(\overline{x}\) be the word produced by replacing all the \(\textbf{A}\)s in \(x\) with \(\textbf{B}\)s and replacing all \(\textbf{B}\)s with \(\textbf{A}\)s.
Now we can produce \(\overline{w}\) by applying Rule (3) followed by Rule (4) to \(w\).
Then we can use Rule (1) and then Rule (2) to get \(\textbf{A} \overline{w}\). Now we can use Rules (3) and (4) again to get \(\overline{\textbf{A} \overline{w}} = \textbf{B}w\).
As we now have ways of adding \(\textbf{A}\) or \(\textbf{B}\) to the start of a word, we can produce any word consisting of \(\textbf{A}\)s and \(\textbf{B}\)s from these four rules starting with the empty word.
