Homework $5$: Turing Decidable Languages

Due date: Wednesday April $17$th at $11$:$00$ PM

Homework solutions are required to be typeset, with the exception of state diagrams, which are allowed to be handdrawn and included in a typeset document. Please see the Course Syllabus for the full homework formatting policy

Double It $[10$ points$]$

Give a high$-$level description of a Turing Machine that decides the language

$L=\{win\{a,b,c{\}}^{**}$: the number $ofa\text{'}sinwis$ more than twice the number $ofb\text{'}s\}$

Note that a string with exactly two times as many a$\text{'}$s as b$\text{'}$s would not be accepted. You must include an explanation of why the TM halts in order to recieve full credit.

$2.$ Now Double It Again $[10$ points$]$

Give a state diagram for the Turing Machine you described in question $(1),$ for the language

$L=\{win\{a,b,c{\}}^{**}$ : the number $ofa\text{'}sinwis$ more than twice the number $ofb\text{'}s\}$

You may $($but do not have to$)$ omit the reject state, under the assumption that if a transition for a tape character is not present on a given state, it transitions to the reject state. If you do include the reject state, you are expected to explicitly indicate all transitions to it$.$ You should use $-$ to indicate a blank tape square, and you may assume that is the symbol on the tape squares immediately preceding and immediately following the first and last tape squares with input symbols, respectively.

Your state diagram for this question may be handwritten.

$3.$ ALL of It$,$ ALLways, ALL Over the Place $[10$ points$]$

Using a reduction, show that the language

$AL{L}_{\text{D}\text{F}\text{A}}=\{($:$D$:$)$;$Dis$ a DFA and $L(D)={}^{**}\}$

is decidable $($i$.$e$.$ for a given alphabet $,D$ accepts all strings composed of that alphabet$),$

You may use any problem we have shown to be decidable in lecture for a reduction. and i want the diagram for this question tooo.