\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 2}
\duedate{Due: Tuesday January 23, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW2} 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}. We recommend that you submit early drafts to Gradescope so that in
case of any technical difficulties, at least some of your work is present. You may update
your submission as many times as you'd like up to the deadline.\\
Your assignments in this class will be evaluated not only on the correctness of your answers, but
also on your ability to present your ideas clearly and logically. Whether you use formal proof techniques or write a more informal argument for why something is true, {\bf your answers should always be well-supported}.\\
{\sc Reading} Sipser Section 1.1, 1.2
\newline
{\sc Key Concepts} Regular languages, closure of the class of regular languages
under certain operations, nondeterministic finite automata (NFA), nondeterministic computation,
spontaneous transitions ($\varepsilon$ arrows).
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]({\bf 10 points})
Consider the DFAs $M_1$ (on the left) and $M_2$ (on the right):
\begin{center}
\includegraphics[width=2in]{hw2_1.png}
\qquad \qquad
\includegraphics[width=2in]{hw2_2.png}
\end{center}
\begin{itemize}
\item[(a)] If we use the general constructions discussed in class and in the book for building a DFA whose language is
\[
\overline{L(M_1)} \cup L(M_2)
\]
how many states would be in this DFA?
Briefly justify your calculation.
\item[(b)] Draw the state diagram that results from this construction and remove any unreachable states.
How many states are left?
\item[(c)] Describe the language $\overline{L(M_1)} \cup L(M_2)$ in set builder notation.
You may find it useful to first describe $L(M_1)$ and $L(M_2)$ in set builder notation
first.
\item[(d)] Use the description from (c)
to draw a DFA with fewer states even than what you saw in part (b). Draw the state diagram in JFLAP
and include the image in your submission.
\end{itemize}
{\it Note}: For parts (b) and (d), you can use the ``test equivalence" feature of JFLAP to
check your work.
\end{problem}
\begin{problem}[2.] Show that the class of regular languages over the alphabet $\{0,1\}$
is closed under the operation $FlipBits(L)$, defined as
\[
FlipBits(L) = \{ w | \text{ $w$ can be obtained from some $w'$ in $L$ by flipping each $0$ in $w'$ to $1$ and each $1$ to $0$}\}
\]
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 DFA $M = (Q, \{0,1\}, \delta, q_0, F)$, and
call the language of this DFA $L$.
\item[Construction] Build a new DFA whose language is $FlipBits(L)$. To do
so, fill in the blanks
\[
M' = (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\}$.}\\
q' &= \underline{\phantom{Fill in the blank here}}
\qquad \text{What is the initial state of $M'$? 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 $M'$? Choose a subset
of $Q'$.}
\end{align*}
\item[Application] Consider the language, $L$, recognized by this DFA (from HW1):
\begin{center}
\includegraphics[width=3in]{hw1.png}
\end{center}
Apply your construction to this DFA and confirm that the language recognized
by the resulting DFA is $FlipBits(L)$.
\end{description}
[[{\it Bonus (not for credit)}: To prove that the construction of correct, we would need to
prove that $L(M') = FlipBits(L)$ for any $L$. Fix an arbitrary but unknown
language $L$. Let $M$ be a DFA recognizing $L$, and construct $M'$ from $M$ as shown above.
Two claims are required
\begin{itemize}
\item[(1)] Assume that some string, call it $w$, is accepted by $M'$. Prove that $w$
is in $FlipBits(L)$.
\item[(2)] Assume that some string, call it $y$, is in $FlipBits(L)$. Prove that
$y$ is accepted by $M'$.
\end{itemize}
Practice your proof techniques by carrying out this justification. ]]
\end{problem}
\begin{problem}[3.] Consider the NFAs $N_1$ (on the left) and $N_2$ (on the right):
\begin{center}
\includegraphics[width=3in]{hw2_3.png}
\qquad
\includegraphics[width=3in]{hw2_4.png}
\end{center}
($N_1$ is described in example 1.33 on page 52.)
\begin{itemize}
\item[(a)] Write out the formal definition of $N_1$ and $N_2$. {\it Notice that $N_2$ appears to be a DFA but we are asking
for its formal description as a NFA. Be careful of types,
especially when describing the transition function of each NFA. }
\item[(b)] Write out $L(N_1)$ and $L(N_2)$ in set builder notation, justifying
each briefly by making specific references to the state diagrams.
\item[(c)] In fact, $L(N_1) = L(N_2)$. You can check this by using the ``test equivalence" feature of JFLAP to compare the two state diagrams. Explain why these two NFAs
are equivalent.
\end{itemize}
\end{problem}
\end{document}