\documentclass[12pt]{cas-handout}
\usepackage{paralist}

\newtheorem{theorem}{Theorem}
\newtheorem{condition}{Condition}
\newcommand{\eps}{\ensuremath{\varepsilon}}

\newcommand{\BAR}{\ |\ }
\newcommand{\two}[2]{\tiny\left[\!\begin{array}{c} #1 \\[-1pt] #2 \end{array}\!\right]}
\newcommand{\three}[3]{\scriptsize\left[\!\begin{array}{c} #1 \\[-1pt] #2 \\[-1pt] #3 \end{array}\!\right]}

\anumber{9}
\title{Regular, Non-Regular, and Context-Free}
\duedate{Wednesday, November 21}

\begin{document}
\maketitle

\begin{itemize}
  \item Emails about this assignment should be directed to
    \helpalias.
  \item The usual collaboration rules apply. You may \emph{discuss} an
    exercise with any other student(s) currently taking CS 81 as long as:
    \begin{compactitem}
      \item You contribute equally;
      \item You come away from this discussion only with
        \emph{understanding in your head} --- no written materials or
        computer notes may be retained;
      \item Your submission is authored solely by you, on a separate
        occasion.
   \end{compactitem}
  \item You should refer only to materials from this semester of CS 81 (lecture
   notes, handouts, textbooks, grutors, profs, etc.).
 \item Make sure your submission includes your name!
\end{itemize}

\hrule

\bigskip\bigskip
\noindent

\begin{enumerate}
\item Review Chapters 8 and 11.1--11.3 of Rich, paying particular attention to
  all the
  examples (in the shaded boxes). Also, read Appendix I.1 (up to I.1.4), and
  Appendix J.1, and Appendix O.

  Come up with (at least) two questions about the reading;
  these should be a question where you're not sure of the answer.
  It may relate to points
  where the book (or the lecture) was confusing, or simply to some related question or
  conjecture that occurs to you while doing the reading.

\item Do Exercise 1(e,j,n,p,q,s) on pages 182--183 of Rich.

\item Do Exercise 7(a,c only) on page 183 of Rich.  [Hint:
you may assume you are given a DFA, NFA, or regular expression,
whichever is most convenient;
then show how to transform it.]

\item Let
\[
\Sigma_3 := \left\{\ \three000, \three001, \three010, \ldots, \three111\ \right\}.
\]
$\Sigma_3$ contains eight size-3 columns of $0$s and $1$s. A string in
symbols in $\Sigma_3$ thus builds three rows of $0$s and
$1$s. Consider each row to be a binary number, and let
\[
 B := \{\ w\in\Sigma_3^* \BAR \mbox{the bottom row of $w$ is the sum
   of the top two rows}\ \}.
\]
For example,
\[
\three001\three100\three110\in B \qquad \mbox{but} \qquad
\three001\three101\not\in B.
\]
Show that $B$ is regular. (Hint: show that $\mathit{reverse}(B)$ is
regular; by a previous problem, then so is
$\mathit{reverse}(\mathit{reverse}(B)) = B$.)

\item Let
\[\Sigma_2 := \left\{ \two00, \two01, \two10, \two11\ \right\}.\]
Consider each of the two rows in $\Sigma_2^*$ to be a binary number,
and let
\[
C := \{\ w\in\Sigma_2^* \BAR \mbox{the bottom row of $w$ is three
  times the top row}\ \}.
\]
For example, $\two00\two01\two11\two00\in C$ but
$\two01\two01\two10\not\in C$. Show that $C$ is regular.
(Hint: show that $\mathit{reverse}(C)$ is regular.)

\item Let $\Sigma_2$ be as in the previous problem, and let
\[
D := \{\ w\in\Sigma_2^* \BAR \mbox{the top row of w is a strictly
  larger number than the bottom row}\ \}.
\]
For example, $\two00\two10\two11\two00\in D$, but
$\two00\two01\two11\two00\not\in D$.  Show that $D$ is regular.

\item Prove that the following languages are context free, by giving a
context-free grammar for each.

\begin{enumerate}
\item $\{\ a^ka^jb^jc^k\ |\ j,k\ge 0\ \}$
%%%
%%%
%%%
\item $\{\ a^ib^j\ |\ i \not= j\ \ \land\ \ i,j > 0\ \}$
%%%
%%%
%%%
%%%
\end{enumerate}

\goodbreak

\item Prove that the following language is \emph{not} context free:
%%%
%%%
  \[\{\ a^nb^{2n}c^n \BAR n \ge 0\ \}\]
%%%
%%%


\end{enumerate}

\end{document}
