\(\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.
…
- 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}\).
If we start with \(\textbf{A}^i\textbf{B}^j\), what effect does Rule (1) have? What about Rule (2)?
Reverse the word, and replace every \(\textbf{A}\) by \(\textbf{B}\), and every \(\textbf{B}\) by \(\textbf{A}\).
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.
Why does creating \(\textbf{A}w\) and \(\textbf{B}w\) from \(w\) solve the problem?
What effect does combining Rule (3) and Rule (4) into a single rule have?
