\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{2} % Homework number
{3} % Week of semester submitted
{1.0} % 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 All strings except \Sym{010} and \Sym{101}.
\item All strings that starts in \Sym{10} and contain
\Sym{111} as a substring.
\item All strings in which every nonempty maximal substring
of consecutive \Sym{1}s is of even length. For instance
\Sym{10011} is not in the language while \Sym{01111000110} is.
\item All strings that do not contain the substring
\Sym{010}.
\item All strings that do not contain the subsequence \Sym{101}.
\end{questions}
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip
\item \OLDHWProblem{100}{Then, shalt thou count to three.}{%
Let $L$ be the set of all strings in $\brc{\Sym0,\Sym1}^*$ that
contain at least three occurrences of the substring \Sym{001}.
\begin{questions}%[(A)]
\item 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 Give a regular expression for $L$, and briefly argue
why the expression is correct.
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip%
\item \OLDHWProblem{100}{Do not affix it.}{%
(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!)
\begin{questions}%[(A)]
\item Let $M = (Q, \Sigma, \delta, s, A)$ be a \DFA. A
state $q \in Q$ is \emphi{bad}, if for all strings
$w \in \Sigma^*$ we have that $\delta^*( q, w) \notin A$.
Let $B(M) \subseteq Q$ be the set of bad states of $M$.
Consider the \DFA $M' = (Q, \Sigma, \delta, s, B(M))$. What
is the language $L(M')$? Prove formally your answer!
\medskip%
\item Prove that if $x \in L(M')$ and $y \in \Sigma^*$,
then $xy \in L(M')$.
\medskip
\item Let $L_1$ and $L_2$ be two 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.
Describe a \DFA $M = (Q, \Sigma, \delta, s, A)$ in terms of
$M_1$ and $M_2$ that accepts
\[
L= \Set{ w }{w \in L_2 \text{ and no prefix of $w$ is
in $L_1$}}
\]
Formally specify the components $Q, \delta, s,$ and $A$ for
$M$ in terms of the components of $M_1$ and $M_2$.
\end{questions}
}{}{}{}%
\end{questions}
\HomeworkEnd{}%