\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 9}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: April 11, 2013 & Due on: April 18, 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+Proof}
For strings $u,v \in \Sigma^*$, we will say $u < v$ to denote that $u$
is less than $v$ in the lexicographic order. An enumerator $N$ is said
to enumerate strings in lexicographic order iff for any strings $u,v
\in {\bf E}(N)$, if $u < v$ then $N$ prints $u$ before $v$. In this
problem, you are required to prove that a language is decidable iff
some enumerator enumerates the language in lexicographic order.
\begin{enumerate}
\item Let $M$ be a Turing machine that decides the language $L$. Show
  that there is enumerator $N$ such that ${\bf E}(N) = L$ and $N$
  enumerates the words in $L$ in lexicographic order.\points{5}
\item Let $N$ be an enumerator that enumerates strings in
  lexicographic order. If ${\bf E}(N)$ is finite then ${\bf E}(N)$ is
  regular and, therefore, decidable. Prove that if ${\bf E}(N)$ is
  infinite then there is a Turing machine $M$ that decides ${\bf
    E}(N)$.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Design}
Show that 
\[
\mathsf{Inf}_{\mathsf{CFG}} = \setof{\tuple{G}\: |\: G
  \mbox{ is a CFG such that } \lang{G} \mbox{ is infinite}}
\] 
is decidable by outlining an algorithm that decides this problem; you
need not prove that your algorithm is correct. \emph{Hint:} You may
find it useful to look at the solution for problem 1 in Discussion 12
(or problem 4.10 in the textbook) and think about the pumping lemma
for CFGs.\points{10}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
Disjoint languages $A$ and $B$ are said to be \emph{recursively
  separable} if there is a decidable language $L$ such that $A
\subseteq L$ and $B \subseteq \overline{L}$. Prove that if $A$ and $B$
disjoint languages such that $\overline{A}$ and $\overline{B}$ are
recursively enumerable then $A$ and $B$ are recursively
separable. \points{10}
\end{problem}

\end{document}
