\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}

% Extra macros for this homework.
\newcommand*{\val}[1]{\operatorname{val}(#1)}
\newcommand*{\pair}[2]
   {\left[\begin{smallmatrix}#1\\#2\end{smallmatrix}\right]}
\renewcommand*{\L}{\mathcal L}

% To indicate number of marks for each question/subquestion.
\newcommand*{\worth}[1]
   {\mbox{}\marginpar{\raggedleft[#1]}\ignorespaces}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Assignment \#\,3}}
\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:}  8\%
\hfill
\strong{Due:}  By 6pm on Wednesday 2 December

\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.
\begin{enumerate}


\item\worth{20}
    In \emph{dyadic} notation,
    natural numbers are represented in base $2$
    using the digits $1$ and $2$ (instead of $0$ and $1$).
    For example, $34$ is represented by
    the dyadic string ``$11122$'' because
    $34 = 1 \cdot 16 + 1 \cdot 8 + 1 \cdot 4 + 2 \cdot 2 + 2 \cdot 1$.
    Note that
    each integer has a \altemph{unique} dyadic representation,
    because there cannot be any leading digits.
    This is unlike binary notation,
    where each integer has infinitely many representations
    (\eg, $34$ is represented by
    each of the infinitely many binary strings
    ``$100010$'', ``$0100010$'', ``$00100010$'', \ldots).
    In particular,
    the unique dyadic representation of $0$
    is the empty string ($\emptystr$).
    For any dyadic string $s \in \{1,2\}^*$,
    $\val{s}$ represents
    the decimal value of $s$
    (\eg, $\val{\text{``122''}} = 10$ and $\val{\text{``\,''}} = 0$).
    \begin{enumerate}

    \item\worth{10}
        Construct a DFA $A_1$ such that
        $A_1$ accepts exactly those dyadic strings whose value is
        a multiple of $5$, \ie,
        \[
            \L(A_1) = \big\{ s \in \{1,2\}* : \val{s} \bmod 5 = 0 \big\}.
        \]
        Justify that $A_1$ is correct by stating
        explicit properties $P_q(s)$ for each state $q$ of $A_1$,
        such that for all strings $s \in \{1,2\}^*$,
        $\delta^*(q_0,s) = q \iff P_q(s)$
        (where $q_0$ is the initial state of $A_1$).
        \altemph
           {Do \strong{not} write a formal proof of correctness for $A_1$.
            Simply give the properties for each state.}

        (\textsc{Hint}:
        Figure out how the values $\val{s1}$ and $\val{s2}$ relate to
        $\val{s}$ for any dyadic string $s$.
        Then, consider what you know about
        the possible values of $x \bmod 5$, for any integer $x$,
        and use this to help in the design of your DFA.)

    \item\worth{10}
        Construct a regular expression $R_1$ such that $\L(R_1) = \L(A_1)$.

        Justify that $R_1$ has this property.
        If you are using a construction from class, show your work, \ie,
        explain what you are doing at each step of your construction.

    \end{enumerate}


\item\worth{20}
    Consider the language
    $L_2 = \big\{ x \in \{0,1\}^* : x$ does \emph{not} contain $000 \big\}$.
    Give a regular expression $R_2$ such that $L_2 = \L(R_2)$.
    Write a careful, detailed proof that $L_2 = \L(R_2)$.

    To some degree, your mark will be inversely proportional to
    the length of your regular expression, \ie,
    you will be rewarded for coming up with
    a regular expression as short as possible.


\item\worth{20}
    Let $\Sigma = \left\{\pair00,\pair01,\pair10,\pair11\right\}$
    be the alphabet of all $2 \times 1$ matrices
    consisting of elements from $\{0,1\}$.

    A string of symbols in $\Sigma$ gives two rows of $0$s and $1$s.
    Consider each row to be a natural number written in binary, and let
    \[
        L_3 = \big\{ x \in \Sigma^* :
        \text{the bottom row of $x$ is smaller than the top row}\big\}.
    \]
    For example,
    $\pair11\pair00\pair10\pair01 \in L_3$ because $1010 > 1001$, but
    $\pair01\pair10\pair01 \notin L_3$ since $010 < 101$.
    Construct a DFA $A_3$ that accepts $L_3$ and
    write a careful, detailed proof that $\L(A_3) = L_3$.

    To some degree, your mark will be inversely proportional to
    the size of your DFA, \ie,
    you will be rewarded for coming up with
    a DFA as small as possible.


\item\worth{20}
    Consider $L_4= \big\{ 0^n 1^m 2^{n-m} : n \ge m \ge 0 \big\}$.
    \begin{enumerate}

    \item\worth{10}
        Write a careful, detailed proof that $L_4$ is not regular.

    \item\strong
           {BONUS!
            \altemph{See the bulletin board announcement for details.}}

        Give a context-free grammar that generates $L_4$.
        Write a careful argument that your CFG is correct, \ie,
        that it generates every string in $L_4$ but
        no string outside $L_4$.

    \end{enumerate}


\end{enumerate}

\end{document}