Problem 1:\\

Prove that for any integer $k > 0$, there is a language $L$ such that 

\begin{enumerate}[label=(\alph*)]
    \item $L$ can be recognized by a DFA with $k$ states
    \item No DFA with less than $k$ states recognizes $L$
\end{enumerate}

Problem 2:\\

Design a DFA that recognizes the following language over the alphabet $\{0,1\}$.  Provide a proof of correctness. 

$\{ w \vert \text{ $w$ contains an even number of $0$s and the substring $010$} \}$

Problem 3:\\

begin{enumerate}[label=(\alph*)]
    \item Let \(A \subseteq \Sigma^*\) be a regular language, and let
    \[
    M=(Q,\Sigma,\delta,q_0,F)
    \]
    be a DFA recognizing \(A\).

    Define a new DFA
    \[
    M'=(Q,\Sigma,\delta,q_0,Q\setminus F).
    \]

    What language does \(M'\) recognize? Prove your answer.

    What general conclusion can you draw from this construction about regular
    languages?

    \item Consider the language
    \[
    L=
    \{w\in\{a,b\}^*
    \mid
    w \text{ has an odd number of \(b\)'s and contains the substring } ab\}.
    \]

    Write \(L\) as the intersection
    \[
    L=L_1\cap L_2
    \]
    of two simpler languages. Clearly define \(L_1\) and \(L_2\).

    \item Construct a DFA recognizing \(L_1\) and a DFA recognizing \(L_2\).

    For each DFA, prove that it recognizes the intended language.

    \item Assume that you have already proved that regular languages are closed
    under union. Argue that $L$ is regular.
\end{enumerate}