\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{Group Homework 3}
\duedate{Due: Saturday February 3, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning.\\
{\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), nondeterministic computation,
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$:
\begin{center}
\includegraphics[width=2in]{hw3_4.png}
\end{center}
(from this week's individual HW assignment).
\begin{itemize}
\item[(a)] In JFLAP, draw the state diagram that results from the algorithm in Theorem 1.47
to construct an NFA recognizing $L(M) \circ L(M)$. Export the image and include it
in your submission. You do not need to justify your answer for this part of this question.
\item[(b)] In JFLAP, draw the state diagram that results from the algorithm in Theorem 1.49
to construct an NFA recognizing $(L(M))^*$. Export the image and include it
in your submission. You do not need to justify your answer for this part of this question.
\item[(c)] Construct an NFA that recognizes $\overline{L(M)}$.
Draw the state diagram in JFLAP and include the image in your submission.
Also, informally justify your design, either by explaining the role of each
state or by citing the algorithms you used to construct it.
{\it Hint: there are (at least) two ways to approach this design problem.
The first way would be to
write $L(M)$ set theoretically, compute its complement, and then
design an NFA from scratch. The second way would be to convert the
NFA to an equivalent DFA, and then use the algorithm for constructing a DFA
for the complement of the language of a DFA.}
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Consider the function from $\{0,1\}$ to
$\{a,b\}^*$ given by $h(0) = a$, $h(1) = ab$.
We can extend $h$ to operate on strings by defining
$h(w) = h(w_1) h(w_2) \cdots h(w_n)$ where $w = w_1 \cdots w_n$ and
each $w_i \in \{0,1\}$.
For example, $h(010) = aaba$. Extending $h$ to languages over
$\{0,1\}$, we define $h(L) = \{ h(w) \st w\in L\}$ for any $L\subseteq \{0,1\}^*$.\\
Devise a general construction that, given a DFA $M$ over the alphabet $\{0,1\}$,
builds a (DFA or NFA) $M'$ over the alphabet $\{a,b\}$ that recognizes
$h(L(M))$.\\
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 or NFA) whose language is $h(L)$.
\item[Application] Consider the language, $L$, recognized by this DFA (from
a previous homework):
\begin{center}
\includegraphics[width=2in]{hw1.png}
\end{center}
Apply your construction to this DFA and confirm that the language recognized
by the resulting (DFA or NFA) is $h(L)$.
\end{description}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Consider the language $L = \{ uw \st \text{$u$ and
$w$ are strings over $\{0,1\}$ and have the same number of $1$s} \}$
(from this week's individual homework).
\begin{itemize}
\item[(a)] Prove that $L = \{ v \in \{0,1\}^* \st \text{$v$ has an even number of $1$s} \}$,
and that $L$ is a regular set.
\item[(b)] Prove that the language $L' = \{ u0w \st \text{$u$ and $w$ are strings over
$\{1\}$ and have the same length} \}$ is not regular.
\end{itemize}
\end{problem}
\end{document}