\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{enumerate}
\usepackage{utf8}

\topic{Automata}
\homework{7}

\begin{document}
\maketitle

\begin{exercises}
\item Draw a DFA that recognizes strings in $\{a,b\}^*$ having an even
number of $a$s and an odd number of $b$s.

\bigskip
\item The set $S$ of strings of balanced parentheses is defined inductively by
the following three rules:
\begin{enumerate}[i.]
\item $ε \in S$
\item If $x \in S$ then the string ``($x$)'' is in $S$
\item If $x$ and $y$ are in $S$, then $xy \in S$
\end{enumerate}

For example, the string $(()())() \in S$, but $())(()$ is not.

\begin{enumerate}
\item Justify the statement $(()())() \in S$ using the rules above.
\item Use structural induction to prove that for all $x \in S$, $x$ has the same
number of left parentheses as right parentheses.
\item Use the pumping lemma to show that $S$ is not DFA-recognizable.
\end{enumerate}

\bigskip
\item (Optional, not graded) get ready to enjoy a relaxing break!

\end{exercises}

\end{document}
