\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor,multicol}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Homework 3}
\duedate{Due: Sunday April 23, 2017}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
Upload a {\bf single file} to Gradescope for each group.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
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 Sections 1.2, 1.3
\newline
{\sc Key Concepts} Nondeterministic
finite automata (NFA), nondeterministic computation, $\varepsilon$ arrows, equivalence of
NFA and DFA, regular expressions, equivalence between languages described
by regular expressions and languages recognized by automata.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 8 points})
\begin{itemize}
\item[(a)] {\bf True or False} For every regular language, there is a
DFA that has {\bf exactly one accepting state} (i.e.\ $|F| = 1$) that recognizes the
language. Briefly justify your answer.
\item[(b)] {\bf True or False} For every regular language, there is an
NFA that has {\bf exactly one accepting state} (i.e.\ $|F| = 1$) that recognizes the
language. Briefly justify your answer.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points})
Consider the language
\[
L = \{ w \in \{a,b,c\}^* ~|~ w~\text{ends with an $a$} \}
\]
\begin{itemize}
\item[(a)] What is $L^*$? Briefly justify your answer.
\item[(b)] Use $L$ as a counterexample to show that the following construction
{\bf does not} prove the closure of the set of regular languages under the
star operation. That is, you should design an NFA recognizing $L$
and show that the constructed automaton $\hat{N}$ does not
recognize $L^*$. For full credit, include
the state diagram for $N$ and for the NFA $\hat{N}$ defined in this construction
(briefly justifying each of them),
and then explain why $L(\hat{N}) \neq L^*$.
{\bf Construction}: Let $N = (Q, \Sigma, \delta, q_0, F)$ be an NFA. Construct
$\hat{N} = (Q, \Sigma, \hat{\delta}, q_0, \hat{F})$, where the states of $\hat{N}$
are the states of $N$, the alphabet of $\hat{N}$ is the alphabet of $N$,
the start state of $\hat{N}$ is the start state of $N$, and
\begin{itemize}
\item $\hat{F} = \{ q_0 \} \cup F$
(so that the start state is guaranteed to be an accept state), and
\item
\[\hat{\delta}(q, x) = \begin{cases}
\delta(q,x) \cup \{ q_0 \} \qquad &\text{if $q \in F$ and $x= \varepsilon$} \\
\delta(q,x) \qquad &\text{otherwise}
\end{cases}
\]
for any $q \in Q$ and $x \in \Sigma_\varepsilon$, so that there is a
spontaneous transition from any accepting state back to the initial state.
\end{itemize}
\item[(c)] Use the construction from Theorem 1.49 to construct a NFA recognizing
$L^*$. For full credit, include
the state diagram for $\tilde{N}$ based on your diagram for $N$ from part (b).
For reference, here is the construction from page 62 of the textbook.
{\bf Construction}: Let $N = (Q, \Sigma, \delta, q_0, F)$ be an NFA. Construct
$\tilde{N} = (\tilde{Q}, \Sigma, \tilde{\delta}, \tilde{q}, \tilde{F})$,
the alphabet of $\tilde{N}$ is the alphabet of $N$, but
\begin{itemize}
\item the states of $\tilde{N}$ include a new state $\tilde{Q} = Q \cup \{\tilde{q}\}$,
\item the new state is the start state of $\tilde{N}$,
\item $\tilde{F} = \{ \tilde{q} \} \cup F$
(so that the new start state is guaranteed to be an accept state), and
\item
\[\tilde{\delta}(q, x) = \begin{cases}
\delta(q,x) \cup \{ q_0 \} \qquad &\text{if $q \in F$ and $x= \varepsilon$} \\
\delta(q,x) \qquad &\text{if $q \in F$ and $x \in \Sigma$} \\
\delta(q,x) \qquad &\text{if $q \in Q$ and $q \notin F$} \\
\{ q_0 \} \qquad &\text{if $q = \tilde{q}$ and $x = \varepsilon$} \\
\emptyset\qquad &\text{if $q = \tilde{q}$ and $x \in \Sigma$} \\
\end{cases}
\]
for any $q \in Q$ and $x \in \Sigma_\varepsilon$, so that there is a
spontaneous transition from any accepting state back to the initial state.
\end{itemize}
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 8 points}) Let $\Sigma = \{ 0,1\}$. Listed below
are ten regular expressions, each describing one of five different languages.
Pair the equivalent regular expressions and briefly express the language
they describe in English. You do not need
to justify why the regular expressions describe
this language for this question. One pair is done for you as an example.
\begin{multicols}{2}
\begin{itemize}
\item[A.] $(10)^* \cup (01)^* \cup (1(01)^*001)$
\item[B.] $(0 \cup 1)^*$
\item[C.] $0 (10)^*1 \cup \varepsilon$
\item[D.] $((01)^* \cup (10)^*)(01 \cup \varepsilon)$
\item[E.] $(01)^* \cup 01(01)^*01$
\item[F.] $(0^*10)^*$
\item[G.] $(0 \cup 10)^* 10 \cup \varepsilon$
\item[H.] $0^*(0^*10^*10^*)^*$
\item[I.] $(0^*1^*)^*$
\item[J.] $(0^*10^*1)^*(0\cup \varepsilon)^*$
\end{itemize}
\end{multicols}
{\bf Example} B. and I. both represent the same language, the language
of {\bf all} strings over $\{0,1\}$.
\end{problem}
\begin{problem}[4.] ({\bf 8 points})
Find a DFA recognizing the {\bf complement} of the language described
by the regular expression over $\{a,b\}$
\[
a(abb)^* \cup b
\]
For full credit, use the procedure given in Theorem 1.54 to convert
this regular expression to an NFA. Then, convert the NFA to an equivalent DFA,
and then form
the DFA that recognizes the complement. Include and label the state diagrams for each
of these intermediate machines.
\end{problem}
\begin{problem}[5.] ({\bf 1 point})
As part of a multi-year study, certain components of this course are
being studied for their effectiveness in improving the learning environment and
outcomes of this class. Please indicate whether you consent
to have your anonymized data included in the study analysis.
\begin{center}
{\bf Consent form:} \url{https://goo.gl/forms/Rw4rQinyK5ukZxbO2}
\end{center}
You will receive credit for indicating that you completed the consent form, whether
or not you choose to participate in the study. Just as in homework 1, we're
using the honor system: to declare that you have read an completed the form,
simply include the statement ``I completed the consent form" (if you're working
individually) or ``Each group member completed the consent form" (if you're working
in a group) as this homework question's answer.
\end{problem}
\end{document}