\documentclass{article}
\usepackage{fullpage}

\input{macros}

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

\newcommand{\tile}[2] {\left[ \frac{#1}{#2} \right]}

\author{}
\date{}

\begin{document}

\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Problem Set 9}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: April 18, 2013 & Due on: April 25, 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 23 and 24.

\begin{problem}{Comprehension+Proof}
The Post Correspondence Problem (PCP) is the following. Given a set of
tiles with two strings, one on the top and the other at the bottom,
you want to determine if there is a list of these tiles (repetitions
allowed) so that the string obtained by reading the top symbols is the
same as the string obtained by reading the bottom symbols. This list
is called a ``match''. For example, consider the set of tiles
\[
\left\{ \tile{b}{ca}, \tile{a}{ab}, \tile{ca}{a}, \tile{abc}{c}\right\}
\]
If we consider the sequence of tiles
\[
\tile{a}{ab}\tile{b}{ca}\tile{ca}{a}\tile{a}{ab}\tile{abc}{c}
\]
the top string is $a\cdot b\cdot ca\cdot a\cdot abc = abcaaabc$ while
the bottom string is $ab\cdot ca\cdot a\cdot ab\cdot c = abcaaabc$, is
the same. However, not all sets of tiles have a match. For example,
\[
\left\{ \tile{abc}{a},\tile{ca}{a},\tile{acc}{ba}\right\}
\]
does not have a match. More formally, given 
\[
P = \left\{ \tile{t_1}{b_1},\tile{t_2}{b_2}, \ldots \tile{t_k}{b_k}\right\}
\]
we need to determine if there is a sequence $i_1,i_2,\ldots i_n$,
where every $i_j \in \{1,2,\ldots k\}$, such that
$t_{i_1}t_{i_2}\cdots t_{i_n} = b_{i_1}b_{i_2}\cdots b_{i_n}$. Thus, 
\[
\mbox{PCP} = \{\tuple{P}\: |\: P \mbox{ is a set of tiles that has a match}\}
\]
The $\mbox{PCP}$ problem is known to be undecidable; interested
students can read section 5.2 of Sipser's book.

Consider $\mbox{AMBIG}_{{\rm CFG}} = \{\tuple{G}\: |\: G \mbox{ is an
  ambiguous CFG}\}$. Prove that $\mbox{AMBIG}_{{\rm CFG}}$ is
undecidable by reducing $\mbox{PCP}$ to $\mbox{AMBIG}_{{\rm
    CFG}}$. \emph{Hint:} Given an instance of $\mbox{PCP}$
\[
P = \left\{ \tile{t_1}{b_1},\tile{t_2}{b_2}, \ldots \tile{t_k}{b_k}\right\}
\]
construct a CFG $G$ with rules
\[
\begin{array}{l}
S \rightarrow T\: |\: B\\
T \rightarrow t_1Ta_1\: |\cdots |\: t_kTa_k\: |\: t_1a_1\: |\cdots |\: t_ka_k\\
B \rightarrow b_1Ba_1\: |\cdots |\: b_kBa_k\: |\: b_1a_1\: |\cdots |\: b_ka_k
\end{array}
\]
where $a_1,\ldots a_k$ are new terminal symbols. Prove that this
reduction is correct.\points{10}
\end{problem}

\begin{problem}{Proof}
Let $A,B \subseteq \{0,1\}^*$ be r.e. languages such that $A \cup B =
\{0,1\}^*$ and $A \cap B \neq \emptyset$. Prove that $A \leq_m (A \cap
B)$.\points{10}
\end{problem}

\begin{problem}{Proof}
Prove that a language $A$ is decidable iff $A \leq_m
\lang{0^*1^*}$.\points{10}
\end{problem}

\end{document}
