\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~}
\name{}
\class{CSE 105}
\assignment{Individual Homework 3}
\duedate{Due: Tuesday January 30, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW3} 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 Section 1.2, 1.3, 1.4
\newline
{\sc Key Concepts} Regular languages, closure of the class of regular languages
under certain operations, nondeterministic finite automata (NFA), spontaneous transitions ($\varepsilon$ arrows), equivalence of NFA and DFA and regular expressions,
nonregular languages, pumping lemma.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]({\bf 10 points})
Consider the NFA $M$: \qquad
%\begin{center}
\includegraphics[width=1.7in]{hw3_1.png}
%\end{center}
\begin{itemize}
\item[(a)] According to Theorem 1.45, the NFA, $N$, that would result from the general algorithm for proving that
$L(M) \cup L(M)$ is regular is given by the state diagram:
\begin{center}
\includegraphics[width=1.8in]{hw3_2.png}
\end{center}
\begin{itemize}
\item Draw the computation of $N$ on the input $001$ (it should be a tree of runs, like
that on
page 49).
\item Explain why $L(N) = L(M)$.
\end{itemize}
\item[(b)] For a DFA, switching accept / non-accept states gives a machine that recognizes
the complement of the language of the original machine. Does
\begin{center}
\includegraphics[width=1.7in]{hw3_3.png}
\end{center}
recognize $\overline{L(M)}$? Why or why not?
\item[(c)] Compute a regular expression describing $L(M)$. You can use your earlier
work or use the Theorems in the book to convert $M$ to a DFA and then to a regular
expression. Include enough work to justify your answer.
\end{itemize}
\end{problem}
\begin{problem}[2.] Show that the class of regular languages over the alphabet $\{0,1\}$
is closed under the operation $Reverse(L)$, defined as
\[
Reverse(L) = \{ w \st w^\mathcal{R} \in L\}
\]
A full proof would have three stages: setup, construction, and proof of correctness.
In this exercise you will focus on the setup and construction, and then apply your
construction to an example.
\begin{description}
\item[Setup] Consider an arbitrary NFA $N = (Q, \{0,1\}, \delta, q_0, F)$, and
call the language of this NFA $L$.
\item[Construction] Build a new NFA whose language is $Reverse(L)$. To do
so, fill in the blanks
\[
N' = (Q', \{0,1\}, \delta', q', F')
\]
where
\begin{align*}
Q' &= \underline{\phantom{Fill in the blank here}} \qquad \text{This will
be the set of states for your new machine.} \\
\delta' ( (r,x) ) &= \underline{\phantom{Fill in the blank here}} \qquad \text{For each possible input to the transition function, specify the output.}
\\
&\phantom{Fill in the blank here}\qquad \qquad \text{Notice that $r$ is a state in $Q'$ and $x \in \{0,1, \varepsilon\}$.}\\
q' &= \underline{\phantom{Fill in the blank here}}
\qquad \text{What is the initial state of $N'$? Make sure you choose an element
of $Q'$.}\\
F' &= \underline{\phantom{Fill in the blank here}} \qquad \text{What is the
set of accepting states of $N'$? Choose a subset
of $Q'$.}
\end{align*}
\item[Application] Consider the language, $L$, recognized by this NFA:
\begin{center}
\includegraphics[width=2.5in]{hw3_4.png}
\end{center}
Apply your construction to this NFA and confirm that the language recognized
by the resulting NFA is $Reverse(L)$.
\end{description}
[[{\it Bonus (not for credit)}: To prove that the construction of correct, we would need to
prove that $L(N') = Reverse(L)$ for any $L$. Fix an arbitrary but unknown
language $L$. Let $N$ be a NFA recognizing $L$, and construct $N'$ from $N$ as shown above.
Two claims are required
\begin{itemize}
\item[(1)] Assume that some string, call it $w$, is accepted by $N'$. Prove that $w$
is in $Reverse(L)$.
\item[(2)] Assume that some string, call it $y$, is in $Reverse(L)$. Prove that
$y$ is accepted by $N'$.
\end{itemize}
Practice your proof techniques by carrying out this justification. ]]
\end{problem}
\begin{problem}[3.] Consider the language $L = \{ uw \st \text{$u$ and
$w$ are strings over $\{0,1\}$ and have the same number of $1$s} \}$.
Find the error in the following attempted proof that $L$ is not regular:
\begin{quote}
``Proof" that $L$ is not regular using the Pumping Lemma: Assume
(towards a contradiction) that $L$ is regular. Then the Pumping Lemma
applies to $L$. Let $p$ be the pumping length of $L$. Choose
$s$ to be the string $1^p 0^p 1^p 0^p$, which is in $L$ because
we can choose $u = 1^p 0^p$ and $w = 1^p 0^p$ which each have $p$ 1s.
Since $s$ is in $L$ and has length greater than or equal to $p$, the Pumping
Lemma guarantees that $s$ can be divided into parts $x,y,z$ where $s=xyz$,
$|y| >0$, $|xy| \leq p$, and for each $i \geq 0$, $xy^iz \in L$.
Since the first $p$ letters of $s$ are all $1$ and $|xy| \leq p$, we know
that $x$ and $y$ are made up of all $1$s. If we let $i=2$, we get
a string $xy^iz$ that is not in $L$ because repeating $y$ twice adds $1$s to
$u$ but not to $w$, and strings in $L$ are required to have the
same number of $1$s in $u$ as in $w$.
This is a contradiction. Therefore, the assumption is false, and $L$ is not regular.
\end{quote}
\end{problem}
\end{document}