Review question

# Can we show that all words consisting of $A$s and $B$s can be made? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R9750

## Question

$\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:

1. 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}$.

2. If the current word ends with $\textbf{B}$, the final $\textbf{B}$ can be removed.

1. Show how the word $\textbf{AAAB}$ can be produced.

2. 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:

1. 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}$.

1. Describe precisely all the words that can be produced with these three rules. Justify your answer.

Finally, we add a fourth rule.

1. Reverse the word.
1. 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.