\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 1}
\duedate{Due: Saturday January 20, 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.3, 1.1
\newline
{\sc Key Concepts} Strings, languages, union, concatenation, Kleene star,
regular expressions, language described
by a regular expression, deterministic finite automata
(DFAs), computations, language recognized by a DFA.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]({\bf 10 points})
Consider the alphabet $\Sigma = \{a,b\}$. Here are several descriptions of sets, along with several regular
expressions. Match the ones that describe the languages.
In other words: for each mathematical description of a set, list (any and all) regular expressions
that describe the set. {\bf Remember to justify your answers.}\\
Hint: start by coming up with test strings for each set and checking whether or not they are described by
the regular expressions. For example, is $\varepsilon$ in the set? is
it in the set described by each of the regular expressions?
\begin{multicols}{2}
{\it Mathematical descriptions of sets}
\begin{itemize}
\item[1.] $\{ b^m a^n \st m,n \in \mathbb{Z}^{\geq 0}\}$
\item[2.] $\{ w \in \Sigma^* \st w \text{ does not start with } b\}$
\item[3.] $\{ w \in \Sigma^* \st ba \text{ is a substring of $w$}\}$
\item[4.] $\{ w \in \Sigma^* \st ab \text{ is not a substring of $w$}\}$
\end{itemize}
\columnbreak
{\it Regular expressions}
\begin{itemize}
\item[(i)] $a^* b^*$
\item[(ii)] $b^* a^*$
\item[(iii)] $b (a \cup b)^*$
\item[(iv)] $b^* (a \cup b)$
\item[(v)] $\left( \Sigma ba \right)^*$
\item[(vi)] $\Sigma^* (ba) \Sigma^*$
\end{itemize}
\end{multicols}
{\it Note}: the notation $\mathbb{Z}^{\geq 0}$ refers to the set of nonnegative integers.
Similarly, we could use the notation $\mathbb{Z}^{+}$ to refer to the set of (strictly) positive integers.
[[ This problem was revised to remove the unnecessary mention of DFAs. ]]
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Consider the DFA, $M$, whose state
diagram is given by:
\begin{center}
\includegraphics[width=3in]{hw1.png}
\end{center}
\begin{itemize}
\item[(a)] If $x \in L(M)$, will the string obtained by flipping bits
in $x$ (changing $0$ to $1$ and $1$ to $0$) also be in $L(M)$?
Why or why not?
\item[(b)] True or false: for any string $x$, if $x$ is in $L(M)$ then so is
$x^{\mathcal{R}}$. Prove your answer.
\item[(c)] Write a regular expression that describes $L(M)$.
{\it Hint: Think back to a mathematical description of $L(M)$ from Individual HW1. How does this description
interact with the state diagram, and can you make use of this to design your regular expression? Also, consider checking your work using JFLAP.}
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Suppose you are working with an incoming bitstream (sequence
of bits) that might be truncated (stopped) at any time. Create a DFA to determine if the number
represented by this truncated sequence of bits is an integer multiple of $3$.\\
For example, if the bits are $11001$, then the number being represented is $25$,
which is not an integer multiple of $3$ so this string should be rejected.\\
Alternatively, if the bits are $1100$, then the number being represented is $12$, which is
an integer multiple of $3$ so this string should be accepted.\\
Leading zeros do not change the value of the number being represented. In particular, this means that $0011001$ should be rejected,
that $01100$ should be accepted, and that both $\varepsilon$ and $0$ should be accepted.
Draw the state diagram of your DFA in JFLAP,
export the image as a png or jpg file, and include it as part
of your submission.\\
Informally justify why your state diagram works by briefly describing the role of each state and the transitions between them.
\end{problem}
\end{document}