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

## Solution

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

Apply Rule (1) three times to get $\textbf{AAABBB}$, and then apply Rule (2) twice to give $\textbf{AAAB}$.

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

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:

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.

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.

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.
1. By first applying Rule (1) to $w$ we get $\textbf{A} w \textbf{B}$, and then applying Rule (2) we get $\textbf{A}w$.

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