7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.
A finite automaton is a mathematical model of a simple computing device. A small finite automaton is illustrated below. [Figure] A finite automaton has some finite number of states; the above automaton has three states, labelled $s _ { 0 } , s _ { 1 }$ and $s _ { 2 }$. The initial state, $s _ { 0 }$, is indicated with an incoming arrow. The automaton receives inputs (e.g. via button presses), which might cause it to change state. In the example, the inputs are $a$ and $b$. The state changes are illustrated by arrows; for example, if the automaton is in state $s _ { 1 }$ and it receives input $b$, it changes to state $s _ { 0 }$; if it is in state $s _ { 2 }$ and receives either input, it remains in state $s _ { 2 }$. (For each state, there is precisely one out-going arrow for each input.) Some of the states are defined to be accepting states; in the example, just $s _ { 1 }$ is defined to be an accepting state, represented by the double circle. A word is a sequence of inputs. The automaton accepts a word $w$ if that sequence of inputs leads to an accepting state from the initial state. For example, the above automaton accepts the word $a b a$. (i) Write down a description of the set of words accepted by the above automaton. A clear but informal description will suffice. (ii) Suppose we alter the above automaton by swapping accepting and non-accepting states; i.e. we make $s _ { 0 }$ and $s _ { 2 }$ accepting, and make $s _ { 1 }$ non-accepting. Write down a description of the set of words accepted by this new automaton. Again, a clear but informal description will suffice. (iii) Draw an automaton that accepts all words containing an even number (possibly zero) of $a$ 's and any number of $b$ 's (and no other words). (iv) Now draw an automaton that accepts all words containing an even number of $a$ 's or an odd number of $b$ 's (and no other words). Let $a ^ { n }$ represent $n$ consecutive $a$ 's. Let $L$ be the set of all words of the form $a ^ { n } b ^ { n }$ where $n = 0,1,2 , \ldots$; i.e. all words composed of some number of $a$ 's followed by the same number of $b$ 's. We will show that no finite automaton accepts precisely this set of words. (v) Suppose a particular finite automaton $A$ does accept precisely the words in $L$. Show that if $i \neq j$ then the words $a ^ { i }$ and $a ^ { j }$ must lead to different states of $A$. Hence show that this leads to a contradiction. This page has been intentionally left blank This page has been intentionally left blank This page has been intentionally left blank
(i) [2 marks] $a , a b a , a b a b a , \ldots$. All words composed of alternating $a$ 's and $b$ 's, starting and ending with an $a$. [0pt]
\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
A finite automaton is a mathematical model of a simple computing device. A small finite automaton is illustrated below.\\
\includegraphics[max width=\textwidth, alt={}, center]{3e018931-0964-46fa-8f09-e829097e009e-20_425_497_592_769}
A finite automaton has some finite number of states; the above automaton has three states, labelled $s _ { 0 } , s _ { 1 }$ and $s _ { 2 }$. The initial state, $s _ { 0 }$, is indicated with an incoming arrow. The automaton receives inputs (e.g. via button presses), which might cause it to change state. In the example, the inputs are $a$ and $b$. The state changes are illustrated by arrows; for example, if the automaton is in state $s _ { 1 }$ and it receives input $b$, it changes to state $s _ { 0 }$; if it is in state $s _ { 2 }$ and receives either input, it remains in state $s _ { 2 }$. (For each state, there is precisely one out-going arrow for each input.)
Some of the states are defined to be accepting states; in the example, just $s _ { 1 }$ is defined to be an accepting state, represented by the double circle. A word is a sequence of inputs. The automaton accepts a word $w$ if that sequence of inputs leads to an accepting state from the initial state. For example, the above automaton accepts the word $a b a$.\\
(i) Write down a description of the set of words accepted by the above automaton. A clear but informal description will suffice.\\
(ii) Suppose we alter the above automaton by swapping accepting and non-accepting states; i.e. we make $s _ { 0 }$ and $s _ { 2 }$ accepting, and make $s _ { 1 }$ non-accepting. Write down a description of the set of words accepted by this new automaton. Again, a clear but informal description will suffice.\\
(iii) Draw an automaton that accepts all words containing an even number (possibly zero) of $a$ 's and any number of $b$ 's (and no other words).\\
(iv) Now draw an automaton that accepts all words containing an even number of $a$ 's or an odd number of $b$ 's (and no other words).
Let $a ^ { n }$ represent $n$ consecutive $a$ 's. Let $L$ be the set of all words of the form $a ^ { n } b ^ { n }$ where $n = 0,1,2 , \ldots$; i.e. all words composed of some number of $a$ 's followed by the same number of $b$ 's. We will show that no finite automaton accepts precisely this set of words.\\
(v) Suppose a particular finite automaton $A$ does accept precisely the words in $L$. Show that if $i \neq j$ then the words $a ^ { i }$ and $a ^ { j }$ must lead to different states of $A$. Hence show that this leads to a contradiction.
This page has been intentionally left blank
This page has been intentionally left blank
This page has been intentionally left blank