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

## Suggestion

$\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. 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)?

1. Reverse the word, and replace every $\textbf{A}$ by $\textbf{B}$, and every $\textbf{B}$ by $\textbf{A}$.

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

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?