\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 2}
\duedate{Due: Saturday January 27, 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. 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 on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.\\
{\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})
Show* that the class of regular languages over the alphabet $\{a,b\}$ is closed under
the operation $sheep(L)$, defined as
\[
sheep(L) = \{ baa w \st w \in L \}
\]
(*) A full proof would have three stages: setup, construction, and proof of correctness; you
will only hand in the first two parts of the proof.
\begin{itemize}
\item[(a)] Write out the {\bf setup} and {\bf construction} stages.
\item[(b)] Consider the DFA $M$ whose
state diagram is:
\begin{center}
\includegraphics[width=3in]{hw2_5.png}
\end{center}
Apply your construction to $M$. 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[(c)] With $M$ as defined in part (b), describe the sets $L(M)$ and $sheep(L(M))$ in mathematical notation.
Relate the mathematical description of $sheep(L(M))$ to the state diagram you built in part (b).
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Prove each of the following facts. You should not
need to design any new constructions for these closure proofs: use results that we have
already proved.
\begin{itemize}
\item[(a)] If we remove one string from any nonempty regular set, the resulting set is still regular.
\item[(b)] The subset of a regular set over $\{a,b,c\}$ consisting of just those strings
that don't use the symbol $c$ is regular.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Consider the following language over the alphabet
$\{0,1,2\}$:
\[
L = \{ a_1 \cdots a_n ~|~ n \geq 0 \text{ and } a_1 < a_2, a_2 > a_3, a_3 < a_4, \ldots \}
\]
For example, $0212$, $120$, and $\varepsilon$ are each strings in $L$;
$11$ and $20$ are not in $L$. Describe an NFA with 6 states that recognizes $L$.
Draw the state diagram of your NFA in JFLAP,
export the image as a png or jpg file, and include it as part
of your submission. In addition, briefly justify your construction by explaining the
role that each state plays in computations.
\end{problem}
\end{document}