\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.5in,headsep=.5in-\headheight]{geometry}
\usepackage{amsmath,amssymb}

% Page layout.
\flushbottom  % stretch text to fill up page
\reversemarginpar  % margin notes on the left

% Common symbols and macros.
\input{macros-236}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Exercise \#\,6}}
\rhead{{\bfseries Fall 2009}}
\lfoot{{Dept.\ of Computer Science,
    University of Toronto (St.~George Campus)}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\vspace*{-5ex}

\noindent
\strong{Worth:}  2\%
\hfill
\strong{Due:}  By 6pm on Wednesday 25 November

\vspace{2.5ex}

\noindent
For each question, please write up detailed answers carefully.
Make sure that you use notation and terminology correctly, and
that you explain and justify what you are doing.
Marks \strong{will} be deducted for
incorrect or ambiguous use of notation and terminology, and for
making incorrect, unjustified, ambiguous, or vague claims
in your solutions.

\noindent
For each language $L$ below, give a DFA $A$ for $L$
(\ie, such that $L(A) = L$).
Justify briefly that each of your DFAs is correct---do \strong{not}
write formal proofs; instead,
explain which strings end up at each state and use this
to justify that your DFA accepts every string in $L$ but
no string outside of $L$.
\begin{enumerate}

\item
    $L_1 = \big\{ s \in \{a,b,c\}^* : |s| = 3k$ for some $k \ge 0 \big\}$.

\item
    $L_2 = \big\{ s \in \{0,1\}^* :$ every $0$ in $s$ is
        \emph{eventually} followed by a $1 \big\}$.

    For example, $001 \in L_2$ because
    there is a $1$ following each $0$ in the string, even though
    the first $0$ is not \emph{immediately} followed by a $1$.

\item
    $L_3 = \big\{ s \in \{\triangle,\square\}^* : s$ contains
        an odd number of $\triangle$'s\,$\big\}$.

\end{enumerate}

\end{document}