\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 January 16, 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. Two of the questions on this homework will be graded for fair effort completeness; one will be graded for correctness.\\
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
also on your ability to present your ideas clearly and logically. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported.\\
{\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})
Recall the following definitions (from page 44) on languages (sets of strings) $A,B$:
\bigskip
{\bf Union} $A\cup B = \{x \st x \in A \text{ or } x \in B\}$
\bigskip
{\bf Concatenation} $A\circ B = \{xy \st x \in A \text{ and } y \in B\}$
\bigskip
{\bf Star} $A^* = \{x_1x_2\dots x_k \st k\in\mathbb{Z} \text{ and } k\geq 0 \text{ and each }x_i\in A\}$
\bigskip
For each of the following languages (sets of strings) over the alphabet $\{a,b\}$, answer the following questions:
\begin{itemize}
\item[(a)]
Is $\epsilon$ (the empty string) in the set?
\item[(b)] Classify each string over $\{ a,b \}$ of length $2$ as in the set or not in the set. Briefly justify
each classification.
\end{itemize}
\begin{enumerate}
\item $\{a,b\}\cup\{ab\}$
\item $\{a\}\circ\{a,b,ab\}$
\item $\{w \in \{ab,ba\}^* \st bb \text{ is not a substring of } w\}$
\item The language described by the regular expression $a^* b^*$
\end{enumerate}
\end{problem}
\begin{problem}[2.] In the previous problem, we considered whether the empty string
was an element of certain languages. Now, generalize this approach:
\begin{itemize}
\item[(a)] Describe how you would determine, given a regular expression $R$, if $\varepsilon \in L(R)$.
\item[(b)] Describe how you would determine, given a DFA $M$, if $\varepsilon \in L(M)$.
\item[(c)] Which of these procedures is easier (simpler)? {\it Observation: we'll see that
some models of computation lend themselves more easily to certain applications than others.}
\end{itemize}
\end{problem}
\begin{problem}[3.] Consider the DFA given by the state diagram:
\begin{center}
\includegraphics[width=3in]{hw1.png}
\end{center}
The author of this DFA claims that this DFA's formal definition is:
\[
( \{ q0, q1, q2, q3 \}, \{ 0,1, 2 \}, \delta, q0, q1 )
\]
with $\delta$ given by the table
\begin{center}
\begin{tabular}{c c | c}
State & Character & State \\
\hline
q0 & 0 & q3 \\
q0 & 1 & q1 \\
q1 & 0 & q2 \\
q1 & 1 & q0 \\
q2 & 0 & q1 \\
q2 & 1 & q3 \\
q3 & 0 & q0 \\
q3 & 1 & q2 \\
\end{tabular}
\end{center}
\begin{itemize}
\item[(a)]Explain why they are wrong (there are two mistakes).
\item[(b)]Fix these mistakes and write out the correct formal definition.
\item[(c)]What is the language recognized by this DFA? Briefly justify your answer.
\item[(d)]Change the state diagram slightly to get a DFA that recognizes the language
\[
\{ w \in \{0,1\}^* \st w \text{ has an even number of $0$s and an even number of $1$s} \}
\]
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. {\it Hint: you can open the .jff file provided to you for this state diagram
and modify it.}
\end{itemize}
\end{problem}
\end{document}