\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth,multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\newcommand{\blank}{\textvisiblespace}
\name{}
\class{CSE 105}
\assignment{Individual Homework 6}
\duedate{Due: Tuesday March 6, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW6} must be completed without any collaboration
with other students in this class. The only allowed sources of help for this homework
are the class textbook, notes, and podcast, and the instructional team. Two of the questions on this homework will be graded for fair effort completeness; one will be graded for correctness.
Your homework {\bf must be typed}. \\
{\sc Reading} Sipser Sections 3.2, 3.3, 4.1
\newline
{\sc Key Concepts} Variants of Turing Machines, computational
problems, decidable problems.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 10 points})
The nonnegative powers of a string $w$ are defined recursively as
\[
w^0 = \varepsilon \qquad \qquad
w^1 = w \qquad \qquad
w^{i+1} = w^i \circ w \qquad \text{for $i \geq 0$}
\]
Given a language $L$, consider the operation
$Power(L)= \{w^n\st w\in L ~~and~~ n\geq 0\}$.
\begin{enumerate}
\item[a.]
For $\Sigma = \{0,1\}$ and $L = \{ 0^n1 \st n \geq 0 \}$, give an example of a string
that is in $L^*$ but not in $Power(L)$ and justify your example. \\
(Therefore, we can
conclude that $L^* = Power(L)$ is {\bf not} always true. {\it As an aside (not
for credit), does equality ever hold?})
\item[b.]
Let $E$ be an enumerator that enumerates an infinite language $L$. Consider the high-level description of an enumerator $E'$.
$E'=~$ ``Ignore the input:
\begin{quote}
1. For $i=1,2,3\dots$, repeat the following\\
2. ~~Run $E$ until it prints $i$ strings (recording those strings).\\
3. ~~For each string $x$ in this collection of $i$ strings:\\
4. ~~~~Print $\varepsilon, x,x^2,x^3,\dots,x^i$."
\end{quote}
{\bf True} or {\bf False}: $L(E') = Power(L)$. Briefly justify your answer.
\item[c.]
{\bf True} or {\bf False}: this construction is sufficient evidence to prove that the class of infinite Turing-recognizable languages is closed under the operation $Power()$.
Briefly justify your answer.
\item[d.]
{\bf True} or {\bf False}: this construction is sufficient evidence to prove that the class of infinite Turing-decidable languages is closed under the operation $Power()$.
Briefly justify your answer.
\end{enumerate}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Consider the following computational
problems:
\begin{itemize}
\item[] $EQ_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) = L(B)$} \}$
\item[] $SUB_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) \subseteq L(B)$} \}$
\item[] $DISJ_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) \cap L(B) = \emptyset$} \} $.
\end{itemize}
Is one of these sets a subset of another? Justify your answer.\\
{\it As an aside, all of these problems are decidable (we proved the first in class, the
other two you'll work on for the group homework).}
\end{problem}
\begin{problem}[3.] ({\bf 10 points})
Consider the high level description of the Turing machine $M$:
$M=~$ ``On input $w$:
\begin{quote}
1. If $w= \langle A \rangle $ where $A$ is a DFA then go to step 2, otherwise reject.\\
2. Create a new DFA $A'$ by swapping the accept states of $A$ with the non-accept states of $A$.\\
3. Simulate the TM $M'$ that decides $E_{DFA}$ on $\langle A'\rangle$.\\
4. If it accepts, accept and if it rejects, reject."
\end{quote}
\begin{enumerate}
\item[a.]
Describe $L(M)$.
\item[b.]
Is $L(M)$ decidable? why or why not?
\end{enumerate}
\end{problem}
\end{document}