\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
AB-words are "words" formed from the letters $\mathbf { A }$ and $\mathbf { 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 $\mathbf { A }$, followed by $x$ and ending with $\mathbf { B }$, written $\mathbf { A } x \mathbf { B }$.\\
(2) If the current word ends with $\mathbf { B }$, the final $\mathbf { B }$ can be removed.\\
(i) Show how the word $\mathbf { A A A B }$ can be produced.\\
(ii) Describe precisely all the words that can be produced with these two rules. Justify your answer. You might like to write $\mathbf { A } ^ { i }$ for the word containing just $i$ consecutive copies of $\mathbf { A }$, and similarly for $\mathbf { B }$; for example $\mathbf { A } ^ { 3 } \mathbf { B } ^ { 2 } = \mathbf { A } \mathbf { A } \mathbf { A B B }$.

We now add a third rule:\\
(3) Reverse the word, and replace every $\mathbf { A }$ by $\mathbf { B }$, and every $\mathbf { B }$ by $\mathbf { A }$.

For example, applying this rule to $\mathbf { A A A B }$ would give $\mathbf { A B B B }$.\\
(iii) Describe precisely all the words that can be produced with these three rules. Justify your answer.

Finally, we add a fourth rule:\\
(4) Reverse the word.\\
(iv) Show that every word consisting of $\mathbf { A s }$ and $\mathbf { 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 $\mathbf { A } w$, and (b) the word $\mathbf { B } w$; hence deduce the result.

End of last question

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank