%\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 2019} }
\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{3}{January 30}{\bf {February 6}}
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 Here is an informal description of a 2-Stack
Nondeterministic Pushdown Automata (2-NPDA): the machine is just
like an ordinary NPDA, except there is a second stack that behaves
just like the first. At each step, the machine reads a symbol from
the tape (possible $\epsilon$), pops specified symbols from each
of the two stacks (either may be $\epsilon$), pushes specified
symbols onto each of the two stacks (either may be $\epsilon$),
and moves into a specified state. The machine accepts if there is
some computation on its input string that causes it to reach an
accept state.
\begin{enumerate}
\item Give a formal definition of a 2-NPDA, and a formal
definition of what it means for a 2-NPDA to accept an input
string. Your definition will probably begin with something like
``A 2-NPDA is a 7-tuple...''
\item Give an informal description of a 2-NPDA that decides the
language:
\[L = \{a^nb^nc^n: n \ge 0\}.\]
\item Prove that 2-NPDAs are equivalent to Turing Machines. That
is, show language $L$ is decided by a 2-NPDA if and only if it is
decided by a Turing Machine.
\end{enumerate}
\item Here is an informal description of a Queue Automaton: the
machine is similar to an NPDA, except that the stack (``last in,
first out'' memory) is replaced with a queue (``first in, first
out'' memory). At each step, the machine reads a symbol from the
tape (possible $\epsilon$), dequeues a specified symbol (possibly
$\epsilon$) from the head of the queue, enqueues a specified
symbol onto the tail of the queue (possibly $\epsilon$), and moves
into a specified state. The machine accepts if there is some
computation on its input string that causes it to reach an accept
state.
\begin{enumerate}
\item Give a formal definition of a Queue Automaton, and a formal
definition of what it means for a Queue Automaton to accept an
input string. Your definition will probably begin with something
like ``A Queue Automaton is a 6-tuple...''
\item Prove that Queue Automata are equivalent to Turing Machines.
That is, show language $L$ is decided by a Queue Automaton if and
only if it is decided by a Turing Machine. Hint: repeated pairs of
``dequeue $x$'' and ``enqueue $x$'' operations cyclically shift
the queue in one direction. Can you use a sequence of cyclic
shifts to replace the symbol at the head of the queue? Can you use
a sequence of cyclic shifts to effect a cyclic shift in the {\em
other} direction? For this last part you may want a queue alphabet
that contains all {\em pairs} of symbols from the input alphabet.
\end{enumerate}
\item
$[$worth 6 pts$]$ This problem concerns that language TILE, defined as
follows. Informally, an instance is a collection of $k$ {\em tile types}, together with a list of {\em horizontally
compatible} pairs of tile types, and a list of {\em vertically
compatible} pairs of tile types. An $n \times n$ {\em tiling} is a
placement of tiles into an $n \times n$ grid, so that every pair
of horizontally adjacent tiles is horizontally
compatible, and every pair of vertically adjacent tiles
is vertically compatible; in addition we
require that the tile in the upper left corner is tile type $1$. The
language TILE consists of all those instances for which there exists
an $n \times n$ tiling for all $n \ge 0$.
Formally, the language TILE is the set of those tuples \[\langle
k, H \subseteq [k] \times [k], V \subseteq [k] \times [k] \rangle\] for which the following holds. For all $n \ge 1$
there exists a function $f:[n]\times[n] \rightarrow [k]$ for
which:
\begin{itemize}
\item $f(1,1) = 1$, and
\item $(f(x, y), f(x, y+1)) \in H$ for all $1 \le x \le n$, and $1 \le y \le n-1$,
and
\item $(f(x, y), f(x+1, y)) \in V$ for all $1 \le x \le n-1$ and $1 \le y \le n$.
\end{itemize}
Here, $[n]$ is shorthand for the set $\{1,2,3,\ldots, n\}$. Prove
that TILE is undecidable by giving a reduction from
$\overline{\mbox{HALT}}$ (the complement of the language HALT).
In other words, give a function $R$ mapping instances of $\overline{\mbox{HALT}}$ to instances of TILE, with the property that $R(\langle M, w \rangle)$ is in the language TILE if and only if $\langle M, w \rangle$ is in the language $\overline{\mbox{HALT}}$. Hint: it will be helpful to ``name'' some of your tiles with
triplets of symbols.
\item Prove that a language $L$ is RE if and only if it can be
expressed as
\[L = \{x : \mbox{there exists $y$ for which } \langle x,y\rangle \in R\}\]
where $R$ is a decidable language. In other words, you must prove
that every language of this form is RE, and that every RE language
$L$ has a related decidable language $R_L$ that allows it to be
described in the form above.
\end{enumerate}
\end{document}