\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 1}
\duedate{Due: Tuesday April 10, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW1} 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 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.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}) For each of the following regular expressions over the alphabet $\{a,b\}$, say whether {\bf each one} of the following
strings is an element of the language described by the regular expression. Justifications aren't required for credit for
this question, but it's good practice to think about how you would explain why your answer is correct.
\begin{enumerate}
\item[a.] Regular expression: $(a \cup b)^*$. Strings: (1) $\varepsilon$ (2) $ab$ (3) $bba$
\item[b.] Regular expression: $aa^* \cup bb^*$. Strings: (1) $\varepsilon$ (2) $aa$ (3) $ba$
\item[c.] Regular expression: $(a\cup b^*) \circ (b \cup a^*)$. Strings: (1) $\varepsilon$ (2) $a$ (3) $abba$ (4) $bbb$
\end{enumerate}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Consider the alphabet $\Sigma = \{0,1\}$. Define the sets
\begin{align*}
L_5 &= \{ w \in \{0,1\}^* \st \text{the length of $w$ is a multiple of $5$}\}\\
N_5 &= \{ w \in \{1\}^* \st \text{the length of $w$ is a multiple of $5$}\}\\
B_5 &= \{ w \in \{0,1\}^* \st \text{interpreting $w$ as a binary number (potentially with leading $0$s), $w$ is a multiple of $5$} \}
\end{align*}
Justifications aren't required for credit for
this question, but it's good practice to think about how you would explain why your answer is correct.
\begin{enumerate}
\item[a.] Give an example of a string over $\Sigma$ that is in $L_5$ and in $N_5$ and in $B_5$, or
say None if no such example exists.
\item[b.] Give an example of a string over $\Sigma$ that is in $N_5$ and not in $L_5$, or
say None if no such example exists.
\item[c.] Give an example of a string over $\Sigma$ that is in $B_5$ and not in $L_5$, or
say None if no such example exists.
\item[d.] Give an example of a string over $\Sigma$ that is in $L_5$ and in $N_5$ and not in $B_5$, or
say None if no such example exists.
\end{enumerate}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Consider the DFA, $M$, given by the state diagram:
\begin{center}
\includegraphics[width=2in]{DFA_HW1.png}
\end{center}
The author of this DFA claims that its formal definition is:
\[
M = ( \{ q0, q1, q2, q3 \}, \{ 0,1, 2, 3 \}, \delta, q0, q3 )
\]
with $\delta$ given by the table
\begin{center}
\begin{tabular}{c | c c}
& $0$ & $1$\\
\hline
$q0$ & $q1$ & $q2$ \\
$q1$ & $q2$ & $q3$ \\
$q2$ & $q2$ & $q3$ \\
$q3$ & $q3$ & $q3$ \\
\end{tabular}
\end{center}
\begin{itemize}
\item[a.] There are two mistakes in this formal definition. Fix them and write out the corrected formal definition.
\item[b.] {\bf True or False} The empty string is accepted by this DFA.
\item[c.] {\bf True or False} $L(M)$ is infinite.
\item[d.] {\bf True or False} If $x \in L(M)$, the string obtained by flipping bits
in $x$ (changing $0$ to $1$ and $1$ to $0$) is also in $L(M)$.
\item[e.] {\bf True or False} There is string $x$ such that $x$ is in $L(M)$ and
$x^{\mathcal{R}}$ is in $L(M)$ as well.
\item[f.] {\bf True or False} There is string $x$ such that $x$ is in $L(M)$ but $x^{\mathcal{R}}$ is not in $L(M)$.
\end{itemize}
Justifications aren't required for credit for
this question, but it's good practice to think about how you would explain why your answers are correct.
\end{problem}
\end{document}