$3^{rd}$ Question:

Trading states for symbols

Parts $($a$)$ and $($b$)$ are to be submitted separately to the Tint autograder on GradeScope.

$($a$)$ Tint Design a standard $($one$-$way$)$ Turing machine that started on a blank tape prints the string hello$-$world $($lower case letters$).$ The computation should end in the accept state with the output beginning in the first cell and the head positioned under that cell. All cells other than the first eleven $($containing the output$)$ should be blank. For full credit, your machine should have at most $10$ states $($including the start, accept, and reject states$).$

$($b$)$ Tint Design a standard $($one$-$way$)$ Turing machine that, started on a blank tape prints the string aabbbbaaababbaababaa $($lower case letters$).$ The computation should end in the accept state with the output beginning in the first cell and the head positioned under that cell. All cells other than the first twenty $($containing the output$)$ should be blank. For full credit, your machine should have at most $5$ states $($including the start, accept, and reject states$).$

$($c$)$ Show that for each string win$\{0,1{\}}^{**}$ there exists a standard $($one$-$way$)$ Turing machine

$M_w=(Q,\{0,1\},,,s,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}})$

with $|Q|5$ states that starting on a blank tape in state $s$ ends in state $q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}}$ with the tape content $w$ beginning in the first cell and the head under that cell.

That is$,$ starting on a blank tape, the machine outputs $w$ and stops in $q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}}$ with the head under the first cell.