This question has two parts worth $10$ points each

A$)$Constructing DFAs

For each of the following languages over the alphabet $\backslash$Sigma $=\{0,1\},$ give a DFA that recognizes the language,

and explain why it$$s correct. Try to use as few states as possible.

a$.\{$w in $\backslash$Sigma $|$ w has an odd number of $1$s$\}.$ For instance, $11111$ has five $1$s and is in the language,

and $001000$ has one $1$ and is in the language, while $11001010$ has four $1$s and is not in the

language.

b$.\{$w in $\backslash$Sigma $|$ w starts and ends with the same character$\}.$ For instance, $100101$ starts and ends with $1$

and is in the language, and $001000$ starts and ends with $0$ and is in the language, while

$11001010$ starts with $1$ but ends with $0$ and is not in the language.

c$.\{$w in $\backslash$Sigma $|$ w starts and ends with the same character and has an odd number of $1$s$\}.$

B$)$A DFA and its Language

Consider the following DFA over the alphabet $=\{a,b,c\}$ :

a$.$ Write out the formal definition of this DFA $($as a $5-$tuple$).$ Describe the transition function in a table.

b$.$ What is the language recognized by this DFA? Give a short English description, then explain in

a paragraph why your description is correct.

c$.($BONUS$,10$ additional points$)$ How many strings of length $32$ are accepted by this DFA? Prove

your answer.