\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx}

\begin{document}

\homework{2}{Prof. Nancy Lynch}{Due: 16 February 2005}{Vinod Vaikuntanathan}

\noindent
\begin{problem} {\bf Designing DFAs and NFAs.}
For each of the following, draw a state diagram for a DFA or NFA (as
required) that recognizes the specified language. In all cases the
alphabet is $\{0,1\}$.
\begin{enumerate}
\item[(a)] 
(Sipser, Exercise 1.6, part a) \\
$L_a = \{w| w \mbox{ begins with } 1 \mbox{ and ends with } 0 \}$.
Provide a DFA recognizing $L_a$.
\item[(b)] 
(Sipser, Exercise 1.6, part l) \\
$L_b = \{w| w \mbox{ contains an even number of } 0s, \mbox{ or
contains exactly two } 1s \}$.
Provide a DFA recognizing $L_b$.
\item[(c)] 
(Sipser, Exercise 1.7, part e) \\
$L_c = 0^*1^*0^+$, that is, the set of strings consisting of some
number (possibly zero) of 0s followed by some number of 1s followed by
at least one 0.
Provide an NFA recognizing $L_c$, with exactly three states.
\item[(d)] 
$L_d = \{ w | w \mbox{ contains the substring } 1100 \mbox{ or does
not contain the substring } 1010 \}$.
Provide an NFA recognizing $L_d$.
\end{enumerate}
\end{problem}

\noindent
\begin{problem} {\bf Proving an FA recognizes a language.}
For one of the automata you designed in problem 1, prove that the
machine recognizes {\em exactly} the specified language.  To do this,
you will need to prove that your automaton (1) accepts all strings in
the language and (2) does not accept any string not in the language.
\end{problem}

\noindent
\begin{problem} {\bf NFA to DFA.}
Consider the following state diagram.

\begin{center}
\includegraphics[height=2in]{figs/nfa.eps}
\end{center}
\begin{enumerate}
\item[(a)] The state diagram above represents an NFA
$N=(Q,\Sigma,\delta,q_0,F)$.  Say what each of the components of the
5-tuple is, for this NFA.
\item[(b)] 
Apply the subset construction described in class to obtain a DFA
$M=(Q',\Sigma,\delta',q_0',F')$ that is equivalent to $N$.  State the
corresponding element(s) in $Q',\delta',q_0',F'$, then describe
$\delta'$ via either a transition table or a state diagram.
\end{enumerate}
\end{problem}

\noindent
\begin{problem}
{\bf Showing languages are regular.}
(From Sipser, Problems 1.31 and 1.32) \\
For any string $w = w_1w_2 \ldots w_n$, the reverse of $w$, written $w^{\cal R}$, is the string $w$ in reverse order, $w_n \ldots w_2 w_1$. For any language $A$, let $A^{\cal R} = \{ w^{\cal R}\ |\ w \in A \}$.
  \begin{enumerate}
  \item
  Show that if $A$ is a regular language, so is $A^{\cal R}$.
  \item
  Let $$\Sigma_3 = \Bigg\{ 
\left[ \begin{array}{c} 0 \\ 0 \\ 0 \end{array} \right],
\left[ \begin{array}{c} 0 \\ 0 \\ 1 \end{array} \right],
\left[ \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \right],
\ldots ,
\left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] 
\Bigg\}
$$
$\Sigma_3$ contains all size $3$ columns of $0$s and $1$s. A string of
symbols of $\Sigma_3$ gives three rows of $0$s and $1$s.
  Consider each row to be a binary number and let 
$$B = \{w \in \Sigma_3^*\ |\ \mbox{ the bottom row of } w \mbox{ is the sum
of the top two rows} \}.$$
  Show that $B$ is regular.
  (Hint:  Use part (a)).
  \end{enumerate}
\end{problem}

\noindent
\begin{problem} 

\begin{enumerate}
\item[(a)]
{\bf Closure construction.}
Use the closure construction for concatenation described in class, and
in Theorem 1.47, to show that $L_1 L_2$ is regular, 
where $L_1$ is the set of strings containing 0 in every position that
is a multiple of 3, and $L_2$ is the set of strings of length at least 3.
\item[(b)]
{\bf Regular languages are closed under another operation}
(Sipser, Exercise 1.43) \\
Let $A$ be any language.  Define $DROPOUT(A)$ to be the language
consisting of all strings that can be obtained by removing one symbol
from a string in $A$.
Thus, $DROPOUT(A) = \{ xz | xyz \in A \mbox{ where } x, z \in
\Sigma^*, y \in \Sigma\}$.
Show that the class of regular languages is closed under the $DROPOUT$
operation.
Give both a proof by picture and a more formal proof by construction
as in Theorem 1.47.
\end{enumerate}
\end{problem}

\end{document}