\documentclass[12pt]{amsart}

\newcommand{\lra}{\longrightarrow}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\C}{{\mathbf C}}
\newcommand{\Proj}{{\mathbf P}}
\newcommand{\northpole}{{\mathbf n}}
\renewcommand{\Re}[1]{{\text Re}(#1)}
\renewcommand{\Im}[1]{{\text Im}(#1)}

\include{xy}
\xyoption{all}
\SelectTips{cm}{}
\CompileMatrices

\include{iJSepsf}
\newcommand{\graphillus}[3]{\epsfysize=#1truein
\vbox{\centerline{\epsffile{#2.eps}}\caption{#3}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Assignment from Chapter 2 of Sipser}
\maketitle

Exercises
\begin{itemize}
\item 2.1 (parse trees and derivations),
\item 2.9 (CFG for a specified language),
\item 2.11 (CFG to PDA, either as in Sipser or as in class),
\item 2.13 (describe a CFL, show it is not regular),
\item 2.16 (closure properties of CFLs under the regular operations).
\end{itemize}

Problems
\begin{itemize}
\item 2.22 (show that a language is context-free),
\item 2.27a (show that a CFG is ambiguous),
\item 2.31 (show that a language is not context-free
[try $w=0^\ell1^{2\ell}0^\ell$]),
\item 2.34 (minimum pumping length for a CFL),
\item 2.36 (the converse of the pumping lemma fails) [Use the language
$$
F=\{a^ib^jc^kd^\ell: i,j,k,\ell\ge0\text{ and if $i=1$ then $j=k=\ell$}\}.
$$
Use the pumping lemma to show that $F\cap\mathbf{ab^*c^*d^*}$ is not a CFL.
Explain why this shows that $F$ is not a CFL.  Show that $2$ (or even~$1$)
works as a pumping length for~$F$.]
\item 2.43a (the scramble of a regular language on two letters is a CFL
[some FA recognizes the regular language; describe a corresponding PDA
that recognizes the scramble]).
\end{itemize}

\end{document}
