$1.$ Mark the box next to the single best answer for each of the following.

a$.$ When a Turing Machine $($TM$)$ halts:

The tape is empty

It accepts if it is in a final state and the tape is empty

It accepts if it has read the entire input and it is in a final state

There are no state transitions that can be made, and it is in a final state

Its tape contains the input string, $\backslash ($ s $\backslash ),$ where $\backslash ($ s $\backslash$in$(\backslash$Sigma $\backslash$cup $\backslash$Gamma$)^\{*\}\backslash )$

None of the above

b$.$ For every language recognized by a PDA, there exists a that accepts the same language.

Turing Machine or Linear Bounded Automaton $($recognizer of CSLs$)$

Deterministic PDA

NFA or DFA

None of the above

c$.$ A TM$,$ like the other automata we have studied, may accept or reject its input. And...

It may go into an infinite loop, i$.$e$.$ it may not halt

If it accepts, there will always be an answer $($output$)$ on the tape

If it rejects, the tape will be empty when it halts, i$.$e$.$ all cells will be blank

If it rejects, the tape will contain the input string that was there when it started

d$.$ Which statement best aligns with the definition of a TM $?$

The tape is unbounded; $\backslash ($ Q $\backslash )$ must be finite; $\backslash (\backslash$Sigma $\backslash )$ and $\backslash (\backslash$Gamma $\backslash )$ may be infinite

The tape is unbounded; $\backslash ($ Q $\backslash )$ can be infinite; $\backslash (\backslash$Sigma $\backslash )$ and $\backslash (\backslash$Gamma $\backslash )$ may be infinite

The tape is unbounded; $\backslash ($ Q $\backslash )$ must be finite; $\backslash (\backslash$Sigma $\backslash )$ must be finite

The tape is unbounded; $\backslash ($ Q $\backslash )$ must be finite; $\backslash (\backslash$Sigma $\backslash )$ and $\backslash (\backslash$Gamma $\backslash )$ must be finite

e$.$ A TM $($the "simulator"$)$ can simulate another TM $($the "simulated"$).$

False, because a TM can only simulate a "weaker" automaton e$.$g$.$ PDA, NFA, DFA

True, and the simulator will always halt, i$.$e$.$ it will always accept or reject

True, but the simulator may not halt, e$.$g$.$ due to an accidental infinite loop

True, but the simulator may not halt $-$ and this is the crux of the Halting Problem