\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\HomeworkStart%
{2} % Homework number
{3} % Week of semester submitted
{1.02} % Version
\HWInstructionsStd{}%
%\hrule%
\medskip%
\begin{questions}[start=4]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Regularize this.}{ For each of the
following languages over the alphabet $\brc{\Sym0,\Sym1}$, give
a regular expression that describes that language, and briefly
argue why your expression is correct.
\begin{questions}%[(A)]
\item \points{20} All strings that contain the subsequence
\Sym{101}.
\item \points{20} All strings that do not contain the
subsequence \Sym{111}.
\item \points{20} All strings that start in \Sym{11} and
contain \Sym{110} as a substring.
\item \points{20} All strings that do not contain the
substring \Sym{100}.
\item \points{20} All strings in which every nonempty
maximal substring of consecutive \Sym{0}s is of length
1. For instance \Sym{1001} is not in the language while
\Sym{10111} is.
\end{questions}
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip
\item \OLDHWProblem{100}{Then, shalt thou find two runs of three.}{%
Let $L$ be the set of all strings in $\brc{\Sym0,\Sym1}^*$ that
contain the substrings \Sym{000} and \Sym{111}.
\begin{questions}%[(A)]
\item \points{60} Describe a \DFA that over the alphabet
$\Sigma = \brc{\Sym0,\Sym1}$ that accepts the language $L$.
Argue that your machine accepts every string in $L$ and
nothing else, by explaining what each state in your \DFA
\emph{means}.
You may either draw the \DFA or describe it formally, but
the states $Q$, the start state $s$, the accepting states
$A$, and the transition function $\delta$ must be clearly
specified.
\item \points{40} Give a regular expression for $L$, and
briefly argue why the expression is correct.
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip%
\item \OLDHWProblem{100}{Construct This}{%
% (This exercise is about writing things formally -- it is not
% difficult once you have cut through the formalism. In short,
% don't panic - you can do it!)
Let $L_1$ and $L_2$ be regular languages over $\Sigma$ accepted
by \DFAs $M_1 = (Q_1, \Sigma, \delta_1, s_1, A_1)$ and
$M_2 = (Q_2, \Sigma, \delta_2, s_2, A_2),$ respectively.
\begin{questions}%[(A)]
\item \points{30}
Describe a \DFA $M = (Q, \Sigma, \delta, s, A)$ in terms of
$M_1$ and $M_2$ that accepts
$ L= L_1 \cup \overline{L_2} \cup \{\epsilon\}$. Formally
specify the components $Q, \delta, s,$ and $A$ for $M$ in
terms of the components of $M_1$ and $M_2$.
\medskip
\item \points{30}
Let $H_1 \subseteq Q_1$ be the set of states $q$ such that
there exists a string $w \in \Sigma^*$ where
$\delta_1^*(q,w) \in A_1$.
Consider the \DFA $M' = (Q_1, \Sigma, \delta_1, s_1,H_1)$. What
is the language $L(M')$? Formally prove your answer!
\medskip%
\item \points{40} Suppose that for every $q \in A_2$ and
$a \in \Sigma$, we have $\delta_2(q,a)= q$. Prove that
$\epsilon \in L_2$ if and only if $L_2= \Sigma^*$.
\end{questions}
}{}{}{}%
\end{questions}
\HomeworkEnd{}%