Q$2(6$ points$)$

Design a Turing machine to delete the $1\text{'}$s from a string of ones and zeros, shifts the tape after deletion of each one$(1)$ so there is no empty

space in the middle of the string after deletion, the Turing machine should update a counter digit $($ from $0$ to $9)$ at the end of the tape with

the number of $1\text{'}$s deleted after each deletion. This is a functional Turing machine so no need for reject state and you can solve it using any

Turing machine. Assume from $(0$ to $9)1\text{'}$s only. You can use a # to separate the counter from the string, The Turing machine must add the #$.$

$1-$Write the outline for the Turing machine $($informally how you think it can be solved$)2-$ Design the diagram $3-$ Use the string $10110$ for

testing, the result should be $00$#$3.$ The informal steps would look like this $10110==>10110$#$==>0110$#$1==>010$#$2==>00$#$3.$ Please give a paper drawn diagram and tracing for the turing machine.