$1.$ Constructing DFAs $(30$ points; each part $10$ points$)$

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$\}.$

$2.$ A DFA and its Language $(20$ points; each part $10$ points$)$

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

a$,$b

start

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.

c c

q$0$ b q$1$ q$2$

b$,$c a

a a$,$b$,$c

q$3$