\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 \#\,5}}
\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 18 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 regular expression $R$ for $L$
(\ie, such that $L(R) = L$).
Justify briefly that each of your regular expressions is correct---do
\strong{not} write formal proofs; instead, just explain
why your regular expression describes 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}