$7.$ Find two errors in the following attempted formal $$definition$$ of a finite automaton:

$$ Q: a set of states

$\backslash$Sigma : a finite input alphabet

$\backslash$delta : Q $\backslash$times $\backslash$Sigma $->$ Q

$$ q$0$ in $\backslash$Sigma

$$ F $$ Q

$1$

$8.[3$ marks$]$ Provide a DFA that recognizes the following language over $\backslash$Sigma $=\{$a$,$b$\}$:

$\{$w $|$ w in $\{$a$,$b$\}$ contains exactly $3$ a$$s$\}$

$9.[3$ marks$]$ Consider the following language:

L $=\{$w $|$ w is a nonempty string of the form a$$b$$c$\}.$

For example, aaabcc and ac are in the language, but cb and abbccb are not. Prove that L

is regular.

$10.[4$ marks$]$ Consider a DFA represented by the following state diagram$\mathrm{.}0$ABCD$0110011$

$($a$)$ Give a formal definition of this DFA as a $5-$tuple $($Q$,\backslash$Sigma $,\backslash$delta $,$ q$0,$ F $).$

$($b$)$ Describe the language recognized by this DFA.

$11.[2$ marks$]$ Which strings are accepted by the following NFA:AB$10,$

$($a$)101010$

$($b$)01011100011$

$($c$)1010111$

$($d$)010111011$

$12.[3$ marks$]$ Design a non$-$deterministic finite automaton $($NFA$)$ for the following language

by providing the state diagram:

$\{$w $|$ w is a binary string containing the substring $00$ and containing the substring $11\}$

Try to minimize the number of states and transitions.

$2$

$13.[3$ marks$]$ Design a simple NFA to recognize the language of the following regular expression,

where $\backslash$Sigma is the set of all letters in the English alphabet:

$\backslash$Sigma $$fun$\backslash$Sigma $\backslash$cup $\backslash$Sigma $$bored$\backslash$Sigma $$

$14.[3$ marks$]$ State which of the following five strings belong to the language of the given regular

expression: $,$ abb, abba, bababb, baaaa.

$($a$)($a $\backslash$cup b$)$ab$($a $\backslash$cup b$)$

$($b$)$ b$$ab$$ab$$

$($c$)$ a $\backslash$cup $($a$$b$)$

$15.[4$ marks$]$ Program in C$.$ Recall the optimized program from the notes that generates $($lists$)$

all binary strings of length n with exactly k $1$s in lexicographic order. Apply this program

to determine how many subsets of $\{1,2,3,...,$ n$\}$ of size k have elements that sum to exactly

m$.$ For instance when n $=6,$ k $=3,$ and m $=8,$ the subset $\{1,3,4\}($which corresponds to

the length n $=6$ binary string $101100)$ has k $=3$ elements and sums to m $=8.$

HAND IN: The source code. Separately, provide output for the following values of n$,$ k$,$ m:

$($a$)3013133$

$($b$)3314177$

$($c$)3615200$

For each case, also provide the clock time your program took to execute in seconds.