%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
\hfill Winter 2023} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Problem Set #1 \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
\vspace{2mm}}
}
\end{center}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\begin{document}
\problemset{2}{January 18}{\bf {January 25}}
Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the text (Sipser). The
full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. {\bf Please turn in your solutions via
Gradescope, by 1pm on the due date.}
\begin{enumerate}
\item
For a positive integer $i$, let $N(i)$ denote its decimal
representation (the usual string we write when writing the number $i$,
with no leading zeros). Let $N'(i)$ denote the string $N(i)$ written
in reverse order (least-significant digit first). Show that the
language \[L = \{N(i)\#N'(i+1): i \ge 1\}\] over the alphabet $\Sigma
= \{0,1,2,3,4,5,6,7,8,9,\#\}$ is recognizable by a pushdown automata.
\item
Give a simple description of the language generated by the
following context-free grammar:
\[S \rightarrow aSb | bSa | SS | \epsilon\]
and {\em prove} that it does in fact generate that language. Once
you know the language, the following hint may help with the proof:
Let $x$ be a string in the language. Prove that the {\em shortest}
(non-empty) prefix of $x$ that is also in the language cannot
begin and end with the same symbol.
\item Show that CFLs are {\em not} closed under intersection. To
do this you should come up with two CFLs $A$ and $B$ with the
property that $C = A \cap B = \{x : x \in A \mbox{ and } x \in
B\}$ is {\em not} a CFL. State the languages you are using and
then:
\begin{enumerate}
\item Prove that $A$ and $B$ are CFLs.
\item Prove that $C = A \cap B$ is not a CFL.
\end{enumerate}
\item Ogden's Lemma and non-context-free languages.
\begin{enumerate}
\item Consider the language $L = \{a^ib^jc^kd^\ell : i = 0 \mbox{
or } j = k = \ell\}$. Prove that $L$ satisfies the conditions of
the CFL Pumping Lemma. In other words, the CFL Pumping Lemma is
{\em incapable} of proving that $L$ is not a CFL (since we cannot
derive a contradiction from the assumption that $L$ is a CFL).
\item The following is a strengthening of the CFL Pumping Lemma:
\begin{lemma}[Ogden's Lemma]
If $L$ is a CFL, then there exists a pumping length $p$ such that
for every $w \in L$ of length at least $p$ {\em and every way of
``marking'' $p$ or more positions in $w$}, $w$ can be written $w =
uvxyz$ such that:
\begin{itemize}
\item for all $i \ge 0$, $uv^ixy^iz \in L$, and
\item $vy$ contains at least 1 marked position of $w$, and
\item $vxy$ contains at most $p$ marked positions of $w$.
\end{itemize}
\end{lemma}
Prove Ogden's Lemma. Hint: assume $L$ is given by a CFG in Chomsky
Normal Form, and consider a parse tree for $w$ in this grammar.
Pick a path from the root to a marked descendant by always
travelling to the child with the greater number of marked
descendants, and find a repeated nonterminal on that path. It may
be useful in the course of the proof to single out ``branch
nodes,'' which are internal nodes whose left and right children
both have marked descendants.
\item Use Ogden's Lemma to prove that the language $L$ from part
(a) is not a CFL.
\end{enumerate}
\item Show that CFL's are {\em not} closed under complement. (The
complement of a language $L \subseteq \Sigma^*$ is $\overline{L} =
\Sigma^* - L$.)
\end{enumerate}
\end{document}