Question $1$: Turing Machines

$($a$)$ Give exactly three differences between how a Turing machine works

and how an NFA works.

$($b$)$ The following is the state diagram of a Turing machine $M_1$ with input

alphabet $\{0,1\}$ and accept state $q_5.($Missing transition arrows are as$-$

sumed to lead to a reject state, not shown.$)$

$($i$)$ Give the sequence of configurations of M$1$ on the input string $01,$

starting with initial configuration q$001.$

$($ii$)$ In general, given any input string w$,$ what will the tape contents

of M$1$ look like after halting?

$($c$)$ Consider a $($single$-$tape$)$ Turing machine M$2,$ with input alphabet $\{$a$,$ b$\}$

that has the following behaviour:

Given any input string w in $\{$a$,$ b$\},$ M$2$ halts in an accepting

state in which the contents of the tape consists of as#bt

$,$

where s is the number of as occurring in w$,$ and t is the

number of bs occurring in w$.($Note the position of the tape

head in this accepting configuration does not matter.$)$

For example, on input aba, M$2$ halts in an accepting state with tape

contents aa#b$,$ while on input babab it halts in an accepting state with

tape contents aa#bbb$.$

$($i$)$ Create a state diagram in JFLAP for M$2,$ using the fewest states

possible. You may assume a two$-$way infinite tape, and the reject

state may be omitted from your diagram. You must include a

screenshot of your diagram in your submitted pdf

$($ii$)$ Give a high$-$level $($i$.$e$.,$ plain English$)$ description of how M$2$ should

work given an input string w in $\{$a$,$ b$\}.$ Your description should

consist of a first line $$On input string w:$$ followed by an enumerated description of each stage of the TM$,$ in the same style as$,$

$($iii$)$ Discuss the time complexity of the specific implementation of M$2$

that you have described in part c$($ii$)$ above. In particular, does it

run in O$($n$)$ steps? O$($n$2)$ steps? Or O$($nk$)$ steps for some k $>2?$

Justify your answer.