\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi

\HomeworkStart%
{2} % Homework number
{3} % Week of semester submitted
{1.06} % Version

\HWInstructionsStd{}%

%\hrule%
\medskip%






\begin{questions}[start=4]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblem{100}{Regular Expressions.}{ 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 do not contain the
           substring \Sym{011}.

	   \item \points{20} All strings that do not contain the
           subsequence \Sym{011}.


           \item \points{20} All strings that start in \Sym{00} and
           contain \Sym{001} as a substring.


	      \item \points{20} All string that contain either the substring
		      \Sym{10} or the substring \Sym{01}, but not both. 
           
           \item \points{20} All strings in which every nonempty
           maximal substring of consecutive \Sym{0}s is of even length. 
	       For instance \Sym{01100} is not in the language while
           \Sym{10000111001} is.
          
       \end{questions}
}{}{}{}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \medskip
    \item \HWProblem{100}{DFA}{%

For each of the below languages $L$, describe a DFA that accepts $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.


       
       \begin{questions}%[(A)]
	\item \points{50} Let $L$ be the set of all strings in $\brc{\Sym0,\Sym1}^*$ that
	contain at least two occurences the substrings \Sym{100}.
 		\medskip
           
	\item \points{50} Let $L$ be the set of all strings in $\set{\Sym0,\Sym1,\Sym{2}}^*$
		that represent ternary numbers divisible by 5 (i.e., numbers in base 3).
		For example, $\Sym{120}$ would be in the language since $120_3 = 
		1\cdot 3^2 + 2 \cdot 3 = 15$, while $\Sym{200}$ would not. (Hint: 
		It might be easier to describe this DFA than to draw it.)


       \end{questions}


    }{}{}
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \medskip%

    \item \HWProblem{100}{More DFAs}{%
       (This exercise is about writing things formally -- it is not
       difficult once you have cut through the formalism.)

       \begin{questions}%[(A)]
       \item \points{30} 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 \points {20} Prove that if $x \in L(M')$ and $y \in \Sigma^*$,
           then $xy \in L(M')$.
           
           
           \medskip
   \item \points{50} Let $L_1$ and $L_2$ be two regular languages over
           $\Sigma$ accepted by the \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 components of $M_1$ and $M_2$.
       \end{questions}
    }{}{}{}%

\end{questions}


\HomeworkEnd{}%