\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG714}{Theory of Computation}{Spring 2008}{25 January 2008}{4}

\begin{center}
\Large{\bf Problem Set 2 (due Friday, February 8)}
\end{center}

{\bf 1. (3 $\times$ 7 = 21 points) Turing-recognizability and -decidability} 

Each of the following three parts gives a definition, description, or
some properties of a language.  In each case, tell whether the
language is:

A\hs  Turing-decidable

B\hs  Turing-recognizable but not Turing-decidable

C\hs   not Turing-recognizable

Justify your answers with proofs, constructions, algorithms, or
examples as needed.

\begin{itemize}
\item[{\bf (a)}] $\{\langle M \rangle: L(M) \mbox{ is infinite}\}$.

\item[{\bf (b)}] $\{\langle M \rangle: L(M) \mbox{ contains at least two
strings}\}$.

\item[{\bf (c)}] $\{\langle G_1, G_2 \rangle: \mbox{$G_1$ and $G_2$ are
context free grammars that generate the same language}\}$.
\end{itemize}

{\bf 2. (9 points) INF\_CFG is decidable}

Given a context-free grammar $G$, show that it is decidable whether
the language generated by $G$ is infinite.  ({\em Hint:} Use the
pumping lemma for context-free languages.)

{\bf 3. (2 $\times$ 8 = 16 points) [Sipser 5.17, 5.18] PCP over unary
and binary alphabets}

We have seen that Post Correspondence Problem over a finite alphabet
is undecidable.
\begin{itemize}
\item[{\bf (a)}] Show that if the alphabet is unary, then PCP is decidable.

\item[{\bf (b)}] Show that if the alphabet is binary, then PCP is undecidable.
\end{itemize}

{\bf 4. (12 points) [Sipser 5.34] Reduction via computation history} 

Consider the problem of determining whether a PDA accepts
some string of the form $\{ww|w \in \{0,1\}^*\}$.  Use the computation
history method to show that this problem is undecidable.

{\bf 5. (12 points) Conditions of Rice's Theorem} 

Show that both conditions of Rice's Theorem are necessary.  That is,
if we drop any one of the conditions then show that there is a
counterexample to the claim of Rice's Theorem.
\end{document}
