\documentclass{article}
\usepackage{fullpage}

\input{macros}

\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}

\author{}
\date{}

\begin{document}

\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Problem Set 8}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: April 4, 2013 & Due on: April 11, 2013
\end{tabular}
\end{center}
\hrule

{\bf Instructions:} This homework has 3 problems that can be solved in
groups of size at most 3. Please follow the homework guidelines given
on the class website; submitions not following these guidelines will
not be graded. 

{\bf Recommended Reading:} Lecture 18, 19, and 20.

\begin{problem}{Comprehension}
Consider the following Turing Machine $M$ with input alphabet $\Sigma
= \{a,b\}$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\node[autst](q0) at (0,2) {$q_0$};
\node[finalst](qa) at (3,2) {$\qacc$};
\node[autst](q1) at (6,2) {$q_1$};
\node[autst](q2) at (9,4) {$q_2$};
\node[autst](q3) at (9,0) {$q_3$};
\node[autst](q4) at (12,2) {$q_4$};
\initialst{q0};
\footnotesize
\draw[->] (q0) -- node[above]{$\blank\rightarrow \blank,\rght$} (qa);
\draw[->] (q0) -- (2,0) -- node[below]{$b\rightarrow X,\rght$} (q3);
\draw[->] (q0) -- (2,4) -- node[above]{$a\rightarrow X,\rght$} (q2);
\draw[->] (q1) -- node[above]{$\blank\rightarrow \blank,\rght$} (qa);
\selfloopabove{q1}{$Y\rightarrow Y,\rght$};
\draw[->] (q1) -- node[right]{$a\rightarrow X,\rght$} (q2);
\draw[->] (q1) -- node[left]{$b\rightarrow X,\rght$} (q3);
\selfloopabovetxt{q2}{$a\rightarrow a,\rght$ $Y\rightarrow Y,\rght$}{2cm};
\draw[->] (q2) -- node[left]{$b\rightarrow Y,\lft$} (q4);
\selfloopbelowtxt{q3}{$b\rightarrow b,\rght$ $Y\rightarrow Y,\rght$}{2cm};
\draw[->] (q3) -- node[right]{$a\rightarrow Y,\lft$} (q4);
\selfloopabovetxt{q4}{$a\rightarrow a,\lft$ $b\rightarrow b,\lft$ $Y\rightarrow Y,\lft$}{2cm};
\draw[->] (q4) -- node[above]{$X\rightarrow X,\rght$} (q1);
\end{tikzpicture}
\end{center}
\end{figure}
The reject state $\qrej$ is not shown, and if from a state there is no
transition on some symbol then as per our convention, we assume it
goes to the reject state.
\begin{enumerate}
\item Give the formal definition of $M$ as a tuple.\points{5}
\item Describe each step of the computation of $M$ on the input
  $baabab$ as a sequence of instantaneous descriptions.\points{3}
\item Describe the language recognized by $M$. Give an informal
  argument that outlines the intuition behind the algorithm used by
  $M$ justifies your answer.\points{2}.
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
In this problem, we will show that for any Turing machine $M = (Q,
\Sigma, \Gamma, \delta, q_0, \qacc, \qrej)$, there is a Type 0 grammar
$G_M = (V,\Sigma,R,S)$ such that $\lang{M} = \lang{G_M}$. Thus, any
problem that can be solved on a Turing machine, can be described using
Type 0 grammars. The construction of the grammar $G_M$ will be based
on the intuition that the rules of $G_M$ will ``simulate $M$
backwards''. More precisely, derivations of $G_M$ will have the form
\[
S \derivest \rhd u_1 \qacc u_2 \lhd \derivest \rhd \config_1 \lhd
\derivest \rhd \config_2 \lhd \derivest \cdots \derivest \rhd
\config_n \lhd \derivest \rhd q_0 w \blank^i\lhd \derivest w
\]
where $q_0 w \movetm \config_n \movetm \config_{n-1} \movetm \cdots
\movetm \config_1 \movetm u_1 \qacc u_2$ is an accepting computation
of $M$ on the input $w$. $\rhd$ and $\lhd$ are special symbols used by
the grammar $G_M$ to ``enclose'' configurations. The variables of
$G_M$ will include $\setof{S,\rhd,\lhd} \cup Q \cup (\Gamma \setminus
\Sigma)$ and any additional variables that might be needed to describe
the following types of derivations: first generate (any) accepting
configuration from $S$; simulate (backwards) a single step of $M$; and
produce the string $w$ from the ``initial configuration'' $\rhd q_0 w
\blank^i\lhd$ by erasing the unnecessary symbols.
\begin{enumerate}
\item Describe a set of rules that produce derivations of the form $S
  \derivest \rhd \config \lhd$ where $\config$ is any accepting
  configuration of $M$.\points{3}
\item Describe a set of rules that simulate $M$ backwards, i.e., have
  derivations $\rhd \config_1 \lhd \derivest \rhd \config_2 \lhd$,
  where $config_1,\config_2$ are configurations of $M$ such that
  $\config_2 \movetm \config_1$.\points{4}
\item Describe a set of rules that produce derivations of the form
  $\rhd q_0w \blank^i\lhd \derivest w$, by ``erasing'' the unnecessary
  symbols.\points{3}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
A \emph{2-PDA} is a pushdown automaton that has \emph{two stacks}. Thus, like
a PDA, it is a nondeterministic machine. In each step, the current
control state, the current input symbol read (which could be
$\emptystr$ meaning nothing is read from the input), the symbol popped
from the first stack (which could be $\emptystr$, meaning that no
symbol is popped), and the symbol popped from the second stack (which
again could be $\emptystr$), determine what the possible next state
is, and the symbols to be pushed onto each of the two stacks (which
could be $\emptystr$ meaning that no symbol is pushed)
are. Additionally, like a PDA, the 2-PDA accepts an input if it
reaches a accepting/final state after reading the entire input,
irrespective of the contents of either of its two stacks.
\begin{enumerate}
\item Give the formal definition of a 2-PDA as a tuple, giving
  the domain and range of the transition function.\points{2}
\item Give the formal definitions of the instantaneous description of
  the 2-PDA, computation on a word, and the language accepted by the
  machine.\points{3}
\item Prove that if $M$ is a (deterministic, single-tape) Turing
  machine then there is a 2-PDA $P$ such that $\lang{P} =
  \lang{M}$. You only need give the construction of the 2-PDA; you do
  not have to prove that your construction is correct.\points{5}
\end{enumerate}
{\bf Aside:} Any recursive program, without dynamic allocation, using
only variables that are Boolean valued (or variables taking values in
some finite set) can be modelled using a pushdown automaton: the
control state gives value to each program variable and the program
counter (resulting in finitely many states since all these take values
in some finite set), and the stack is used to model the call stack of
the program. Thus a 2-threaded program (or multi-threaded program, in
general) can be modelled by a 2-PDA (or a $k$-PDA, for some value of
$k$), where the different stacks model the call stack of each of the
threads. This result suggests that multi-threaded programs (with only
Boolean variables) can compute anything that a general program with
variables of arbitrary type can. This is also to contrast with teh
limited computational power of a PDA with a single stack.
\end{problem}

\end{document}
