Oops!. $..$ ilon did it again.

Professor $$ has helpfully given you several statements and claimed proofs about DFAs and

Turing machines. Unfortunately $($but unsurprisingly$),$ all of them are wrong at least one way!

For each statement, explain whether it is "well formed"$-$i$.$e$.,$ it uses terminology correctly, and

is either true or false. If it is not well formed, describe a small 'repair' that would make it well

formed, and captures $\text{'}$s likely intent. Finally, explain whether the claimed proof is logically

valid for the $($possibly repaired$)$ statement.

$($a$)$ Statement: any DFA $($with alphabet $)$ whose states are all accepting states accepts the

language ${}^{*}.$

Claimed proof: no matter what the input string is$,$ the DFA remains in an accepting

state throughout its computation, so it eventually accepts the string. Therefore, the DFA

accepts every string over the alphabet $,$ which proves the claim.

$($b$)$ Statement: there is a DFA with alphabet $=\{1\}$ that decides the language

$L=\{1^p$:$pis$ prime $\}$

Claimed proof: we describe such a DFA $P.$ It has a state $q_n$ for each non$-$negative integer

$n0,$ and $q_n\text{'}$s only transition $($for the single alphabet character $1)$ is to state $q_{n+1}.$ The

initial state is $q_0,$ and the accepting states are exactly those $q_p$ where $p$ is prime. One can

see that $P,$ when run on an arbitrary input string $1^k,$ ends up at state $q_k$; so$,$ it accepts

if $k$ is prime, and rejects otherwise. Therefore, $P$ decides $L.$

$($c$)$ Statement: Let $M$ be a Turing machine, and $M^{\text{'}}$ be the same Turing machine but with

the accept and reject states swapped. Then the language of $M^{\text{'}}$ is $L(M^{\text{'}})\frac{?}{b}=ar(L(M)),$ i$.$e$.,$ the

complement of the language $L(M)$ of $M.$

Claimed proof: Because the accept and reject states are swapped, $M^{\text{'}}$ rejects every

string that $M$ accepts, and accepts every string that $M$ rejects. So$,$ since $L(M),L(M^{\text{'}})$

are by definition the sets of strings that $M,M^{\text{'}}$ accept $($respectively$),$ we conclude that

$L(M^{\text{'}})\frac{?}{b}=ar(L(M)).$