Let Lsube${}^{*}$ be a language. The complement of $L,$ denoted $L^c,$ is the complement of $L$ in ${}^{*}.$ That is$,$ for

every win${}^{*},$ we have $win{L}^c$ if and only if $w!$inL.

$($a$)$ Given a DFA $M$ recognising a language $L=L(M),$ explain in words how to construct a DFA $M^{\text{'}}$ such

that $L(M^{\text{'}})=L^c.$

$($b$)$ Construct a DFA recognising the following language:

$L=\{win{}^{*}|$ every odd position $ofwis1\}$

Justification not required.

$($c$)$ Now use your method from the first part to draw a DFA for the complement of the language $L$ above.

Justification not required.