\documentclass{article}
\input{6045preamble}


\begin{document}
\homework{1}{Prof. Ron Rivest}{19 February 2002}{Your name goes here}

\begin{problem}
Consider a nondeterministic 
finite automaton with three states (I), (II), (III) and 
the following transition rules:
\begin{itemize}
\item Transition from state (I) to state (I) on input 'a'
\item Transition from state (II) to state (III) on input 'a'
\item Transition from state (I) to state (I) on input 'b'
\item Transition from state (I) to state (II) on input 'b'
\item Transition from state (II) to state (III) on input 'b'
\end{itemize}
In this automaton, state (I) is the start state and state (III)
is the only accepting state.

\textbf{Part A:} Draw a state diagram for this NFA.

\textbf{Part B:} Describe the language recognized by this NFA.

\textbf{Part C:} Use the transformation that we discussed in class to create a DFA which is equivalent
to this NFA. Draw a state diagram for the resulting DFA.

\end{problem}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\begin{problem}
For each of the following, draw a state diagram for a machine that satisfies the stated
property. Additionally, for one of the following, provide a proof that the 
machine you have created recognizes the indicated language. (From Sipser 1.4 and 1.27) 
\begin{enumerate}
\item A Finite Automaton that recognizes the language of binary strings that do not contain the substring 0101.
\item A Finite Automaton that recognizes the language of binary strings that contain at least three 1's. 
\item A Deterministic Finite Automaton that recognizes the language of binary strings that contain exactly two 1's or
an even number of zeros.
\item A Nondeterministic Finite Automaton that recognizes the language of binary strings that contain exactly two 1's or
an even number of zeros. 
\item Let $\Sigma$ be the following alphabet:
$$
\{ (0,0) (0,1) (1,0) (1,1) \}
$$
A string from this alphabet can be interpreted as two binary numbers (a left number and a
right number). For example, the string
$$
(0,1)(1,0)(1,1)(1,0)(0,0)
$$
Can be interpreted as the left number 01110 and the right number 10100. Create a finite
automaton that recognizes the language of strings where the left number is greater than the 
right number.
\end{enumerate}
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here
%
%
%
\end{solution}


\begin{problem}
Consider a new kind of finite automaton called an all-paths-NFA. An all-paths-NFA $M$ is 
a five tuple $(Q, \Sigma, \delta, q_0, F)$ that recognizes $x \in \Sigma^*$ if every
possible computation of M on $x$ ends in a state from $F$. Note, in contrast, that an 
ordinary NFA accepts a string if \emph{some} computation ends in an accept state. Prove
that all-paths-NFAs recognize the class of regular languages.
(Sipser Problem 1.31)
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here
%
%
%
\end{solution}


\begin{problem}
Let $\Sigma$ be a finite alphabet and let $L \subseteq \Sigma^* $ be a language accepted by some 
deterministic finite automaton $M$.  (Sipser Problem 1.27) Prove that 
$$
L' = \{a_1 a_2 a_3 \ldots a_{n-1} a_n \ | \ a_n a_{n-1} \ldots a_3 a_2 a_1 \in L\}
$$
is accepted by some deterministic finite automaton $M'$. (Sipser Problem 1.24)

\end{problem}


\begin{solution}
%
%
%
  Your solution goes here
%
%
%
\end{solution}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: