\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 April 17, 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.\\
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.\\
{\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})
In Individual HW0, we worked with the following operations: For $L$ a set of strings, we can define the following associated sets
\[
L \circ L = \{ uw \st u \in L \text{ and } w \in L \}
\]
\[
DOUBLE(L) = \{ vv \st v \in L \}
\]
\[
STUTTER(L) = \{ w_1 w_1 w_2 w_2 \cdots w_n w_n \st n \geq 0, w_i \in \Sigma \text{ for each $i$ where $1 \leq i \leq n$, and }
w_1 w_2 \cdots w_n \in L \}
\]
Note: $\varepsilon$ is in each of these sets iff it is an element of $L$ itself.\\
Consider the language $E_1 = \{ w \in \{0,1\}^* \st w \text{ ends in $1$} \} = \{ u1 \st u \in \{0,1\}^* \}$. $E_1$ is recognized by each
of the machines below.
\begin{center}
\includegraphics[width=2in]{closure_HW2_1.png}
\qquad
\includegraphics[width=2in]{closure_HW2_2.png}
\end{center}
(The machine on the left may be either a DFA or an NFA because it has exactly one outgoing arrow from each state for each input
symbol, and has no spontaneous transitions. The machine on the right is an NFA.)
\begin{itemize}
\item[a.] Which of the following DFAs, NFAs, and regular expressions recognizes / describes $E_1 \circ E_1$? {\it List the
identifiers of the correct choices; if none do, write ``None".}
\item[b.] Which of the following DFAs, NFAs, and regular expressions recognizes / describes $DOUBLE(E_1)$? {\it List the
identifiers of the correct choices; if none do, write ``None".}
\item[c.] Which of the following DFAs, NFAs, and regular expressions recognizes / describes $STUTTER(E_1)$? {\it List the
identifiers of the correct choices; if none do, write ``None".}
\item[d.] For each of the four machines listed, label it ``DFA" or ``NFA" or ``either".
\end{itemize}
\end{problem}
\begin{center}
\begin{tabular}{|c|c|}
\hline
Regexp 1 & $((00)^*(11)^*)^*(11)$\\
\hline
Regexp 2 & $( 0 \cup 1)^* 1 (0^* 1^*)^*1$\\
\hline
Machine 3 & \includegraphics[width=3in]{closure_HW2_3.png} \\
\hline
Machine 4 & \includegraphics[width=3in]{closure_HW2_4.png} \\
\hline
Machine 5 & \includegraphics[width=3in]{closure_HW2_5.png} \\
\hline
Machine 6 & \includegraphics[width=2in]{closure_HW2_6.png} \\
\hline
\end{tabular}
\end{center}
\noindent {\it Note}: You can download the .jff files for all these machines, open them in JFLAP, and test them on specific inputs and/or
use the `test equivalence" feature of JFLAP to check your work.
\begin{problem}[2.] Consider an arbitrary DFA $M = (Q, \{0,1\}, \delta, q_0, F)$ and
call the language of this DFA $L$. {\bf Fill in the blanks} in the definition of a new DFA whose language is
the result of taking each string in $L$ and replacing each $0$ in the string with $a$ and each $1$ in the
string with $b$. For example, if $L = \{ 0, 001 \}$, then the new language is $\{ a, aab \}$.
The new machine is
\[
M' = (Q', \{a,b\}, \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 \{a,b\}$.}\\
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*}
\end{problem}
\begin{problem}[3.] Consider an arbitrary DFA $M = (Q, \{0,1\}, \delta, q_0, F)$ and
call the language of this DFA $L$. We will define an NFA whose language is
the result of taking each string in $L$ and replacing each $0$ in the string with $aa$ and each $1$ in the
string with $ab$. For example, if $L = \{ 0, 001 \}$, then the new language is $\{ aa, aaaaab \}$.
The idea for this construction is to have two copies of each state to allow us to group the bits read in
as pairs.
The new machine is
\[
M" = (Q", \{a,b\}, \delta", q", F")
\]
where
\begin{align*}
Q" &= Q \times \{1^{st},2^{nd}\} \\
\delta"(~ ((r,1^{st}), a) ~) &= \{ (r,2^{nd}) \} \\
\delta"(~ ((r,1^{st}), b) ~) &= \emptyset \\
\delta"(~ ((r,2^{nd}), a) ~) &= \{ (\delta( (r,0) ),1^{st}) \} \\
\delta"(~ ((r,2^{nd}), b) ~) &= \{ (\delta( (r,1) ),1^{st}) \} \\
q" &= (q_0, 1^{st}) \\
F" &= F \times \{1^{st}\}
\end{align*}
\begin{itemize}
\item[a.] Apply this construction to the DFA from question 1:
\begin{center}
\includegraphics[width=2in]{closure_HW2_1.png}
\end{center}
Draw the resulting state diagram in JFLAP,
export the image as a png or jpg file, and include it as part
of your submission.
\item[b.] Give an example of a string of length $3$ for which the computation of $M''$ on this string
gets ``stuck".
\item[c.] If you were to use Theorem 1.39 on page 55 in the book (the ``subset construction") to write
an equivalent DFA to the NFA you produced in a. , how many states would the DFA have?
Your answer should take into account unreachable states. {\it Extension: (not to submit) is this number optimal?}
\end{itemize}
\end{problem}
\end{document}