On the alphabet $\{0,1\},$ let $L$ be the language of all bitstrings where every $1$ is followed by one, or two, by

no more, $0$s$.$ So$,,10$ and $100$ are in $L,$ but $1000,1001$ and $1$ are not in $L.$

The DFA machine $M$ below accepts this language.

Let $L^{\text{'}}$ be the language of the reverse of all bitstrings in $L$ : all bitstrings where every $1$ is preceded by one, or twi

but no more, $0$s$.$ So since $0100$inL, then $0010in{L}^{\text{'}}.$

A machine which accepts $L^r$ is formed from $M$ by:

reversing each arrow in $M$;

making the start state in $M$ the $($only$)$ accepting state;

making each accepting state in $M$ a start state.

in addition, also make the following two changes, which do not alter the language $L^r$ accepted:

any inaccessible states are removed;

create a new $($single$)$ start state, $S,$ with $l-$transitions from $S$ to the start states described above $($the forme

accepting states of $M).$

Let $M^r$ be the NFA with these changes made.

$($a$)$ Draw the machine $M^r,$ using the same state names as in $M,$ with the new start state called $S.$ Hint: $M^r$ has

states, with $9$ arrows$/$transitions between states.