\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
In this question we will study a mechanism for producing a set of words. We will only consider words containing the letters $a$ and/or $b$, and that have length at least 1 . We will make use of variables, which we shall write as capital letters, including a special start variable called $S$. We will also use rules, which show how a variable can be replaced by a sequence of variables and/or letters. Starting with the start variable $S$, we repeatedly replace one of the variables according to one of the rules (in any order) until no variables remain.

For example suppose the rules are

$$S \rightarrow A B , \quad A \rightarrow A A , \quad A \rightarrow a , \quad B \rightarrow b b .$$

We can produce the word $a a b b$ as follows; at each point, the variable that is replaced is underlined:

$$\underline { S } \rightarrow \underline { A } B \rightarrow A \underline { A } B \rightarrow \underline { A } a B \rightarrow a a \underline { B } \rightarrow a a b b .$$

(i) Show that the above rules can be used to produce all words of the form $a ^ { n } b b$ with $n \geq 1$, where $a ^ { n }$ represents $n$ consecutive $a$ 's.\\
Also briefly explain why the rules can be used to produce no other words.\\
(ii) Give a precise description of the words produced by the following rules.

$$S \rightarrow a b , \quad S \rightarrow a S b .$$

(iii) A palindrome is a word that reads the same forwards as backwards, for example $b b a a b b$. Give rules that produce all palindromes (and no other words).\\
(iv) Consider the words with the same number of $a$ 's as $b$ 's; for example, $a a b a b b$. Write down rules that produce these words (and no others).\\
(v) Suppose you are given a collection of rules that produces the words in $L _ { 1 }$, and another collection of rules that produces the words in $L _ { 2 }$. Show how to produce a single set of rules that produce all words in $L _ { 1 }$ or $L _ { 2 }$, or both (and no other words). Hint: you may introduce new variables if you want.

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank