\documentclass{article}

\input{6045preamble}

\begin{document}

\homework{4}{Prof. Ron Rivest}{Due: 19 March 2003}{Your Name Here}

\begin{problem}
Let $L$ be an undecidable language.  (Note that $L$ may, be
recognizable, or co-recognizable (that is, its complement
may be recognizable), but not both.)

Prove that the language
$$
L' = 0 L \union 1 \overline{L}
$$
is neither recognizable nor co-recognizable.
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\begin{problem}(Sipser 4.19 and 5.12) In this problem, let $w^R$ be the reverse of the
string $w$.

\textbf{Part A:} Let $A$ be the language:
$$
A = \{<M>| \mbox{M is a DFA such that M accepts $w$ if and only if M accepts $w^R$} \}
$$
Prove that $A$ is decidable. (Hint: Theorem 4.5)

\textbf{Part B:} Let $B$ be the language:
$$
B = \{<T>| \mbox{T is a TM such that T accepts $w$ if and only if T accepts $w^R$} \}
$$
Prove that $B$ is undecidable. (Hint: One proof can be based on theorem 5.2 and its proof).
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\begin{problem}
In class we defined a language, $L$,
to be enumeratable if there exists an enumerator, $E$,
such that $L$ is the set of strings that $E$ prints out
at some point during its execution. (Note that any particular string $x \in L$ may
be printed out finitely many times or may be printed out infinitely many times).
In this problem, we consider a related notion which we call \emph{Uber-Enumeratable}.
We say a language is \emph{Uber-Enumeratable} if there exists an enumerator, $E'$,
such that $L$ is the set of strings which are printed out infinitely many times
during the execution of $E'$. 

\textbf{Part A:} Prove that if $L$ is enumeratable than $L$ is \emph{Uber-Enumeratable}.

\textbf{Part B:} Prove that there exists a language, $L'$, such that $L'$ 
is \emph{Uber-Enumeratable} but not enumeratable. (Hint: Consider the language 
$\overline{A_{TM}}$).
\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\end{document}