\documentclass{article}

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

\begin{document}

\homework{2}{Prof. Nancy Lynch}{Due: Tuesday, February 20, 2007}{Elena Grigorescu}



\noindent{\bf Reading:  Sipser, Sections 1.2 and 1.3.}
\\\\
\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 c. 
$L_1 = \{w| w \mbox{ contains the substring } 0101 \}$.
Provide a DFA recognizing $L_1$.
\item[(b)] 
Sipser exercise 1.6, part j.
$L_2 = \{w| w \mbox{ contains at least two } 0s \mbox{ and at most one
  } 1\}$.
Provide a DFA recognizing $L_2$.

\item[(c)] 
Sipser exercise 1.7, part c. 
$L_3 = \{w | w \mbox{ contains an even number of } 0s, 
  \mbox{ or exactly two } 1s \}$.  
Provide an NFA with at most six states that recognizes $L_3$.
\end{enumerate}
\end{problem}

\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}

\begin{problem} {\bf A harder DFA design problem.}
Sipser problem 1.33.

Let
$$\Sigma_2=\left\{\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{0},\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{1},\genfrac{\lbrack}{\rbrack}{0pt}{}{1}{0},\genfrac{\lbrack}{\rbrack}{0pt}{}{1}{1}\right\}.$$
Here, $\Sigma_2$ contains all columns of 0s and 1s of height two.  A string of symbols in $\Sigma_2$ gives two rows of 0s and 1s.  Consider each row to be a binary number and let
$$C =\{w \in \Sigma_2^*|\mbox{ the bottom row of }w \mbox{ is three times the top row} \}.$$
For example, $\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{0}\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{1}\genfrac{\lbrack}{\rbrack}{0pt}{}{1}{1}\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{0} \in C$, but $\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{1}\genfrac{\lbrack}{\rbrack}{0pt}{}{0}{1}\genfrac{\lbrack}{\rbrack}{0pt}{}{1}{0} \not\in C$.  Provide an NFA that recognizes $C$.

\end{problem}
\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$.
  Define the components of $M$, $Q'$,$\delta'$, $q_0'$, $F'$ precisely.  You may describe $\delta'$
  via either a transition table or a state diagram.
\end{enumerate}
\end{problem}


\begin{problem} {\bf Regular languages are closed under the star operation.}
Sipser exercise 1.15. Give a counterexample to show that the following
construction fails to prove Theorem 1.49, the closure of the class of
regular languages under the star operation.\footnote{In other words,
  you must present a finite automaton, $N_1$, for which the
  constructed automaton $N$ does not recognize the star of $N_1$'s
  language.}  
Let $N_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ be an NFA that recognizes $A_1$.
Construct NFA $N=(Q_1,\Sigma,\delta,q_1,F)$ as follows.  
$N$ is supposed to recognize $A_1^*$.
\begin{enumerate}
\item[(a)] The states of $N$ are the states of $N_1$.
\item[(b)] The start state of $N$ is the same as the start state of $N_1$.
\item[(c)] $F=\{q_1\} \cup F_1$.  The accept states $F$ are the old accept states plus its start state.
\item[(d)] Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_{\varepsilon}$,
$$\delta(q,a)=
\begin{cases}
\delta_1(q,a) & q \not\in F_1 \mbox{ or } a \neq \varepsilon \\
\delta_1(q,a) \cup \{q_1\} & q \in F_1 \mbox{ and } a=\varepsilon.
\end{cases}$$
\end{enumerate}
(Suggestion: convert this formal construction to a picture, as in Figure 1.50 of Sipser.)
\end{problem}

\begin{problem} {\bf Showing closure under other operations.}
In each of the following parts we define an operation on a language $A$.
Show that the class of regular languages is closed under that
operation.
\begin{enumerate}
\item[(a)] 
$Reverse(A) = \{w | \mbox{ the reverse of } w \mbox{ is in } A \}$.
\item[(b)]
$Extend(A) = \{w | \mbox{ some prefix of } w \mbox{ is in } A\}$.
(A string $x$ is a {\bf prefix} of string $y$ if a string $z$
exists where $xz=y$.)
\item[(c)] 
$Suffix(A) = \{w | w \mbox{ is a suffix of some string in } A \}$.
(A string $x$ is a {\bf suffix} of string $y$ if a string $z$
exists where $zx=y$.)
\end{enumerate}
\end{problem}

\end{document}

