%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,oneside,english,english,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{amssymb}
\usepackage[dvips]{color}
\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{plain}    
 \newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
 \newtheorem{prop}[thm]{Proposition} %%Delete [thm] to re-start numbering
 \theoremstyle{definition}
 \newtheorem{defn}[thm]{Definition}
 \theoremstyle{definition}
 \newtheorem{example}[thm]{Example}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\R}{\field{R}}
\newcommand{\Z}{\field{Z}}
\newcommand{\Q}{\field{Q}}
 \newcommand{\lyxaddress}[1]{
   \par {{\bf R}aggedright #1 
   \vspace{1.4em}
   \noindent\par}
 }


\begin{document}

\begin{center}
{\Large{\color{red}Homework 2 (NFA, Equivalence of NFA and DFA, and Regular Languages)}}

{\it Due Monday, Feb 19, 07, at 3:00 PM in Class}

{\it Due: Thursday}
\end{center}

\begin{enumerate}

\item Transform the following NFA $N=(Q,\{0,1\},\delta,q_0,F)$ to a DFA (it suffices to give the STD of the DFA). 
$Q=\{q_0,q_1, \cdots, q_5\}$, $F=\{q_3,q_4\}$, and $\delta$ is as follows:

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \\
$\delta$ &  0 & 1 & $\epsilon$\\
\hline
$q_0$ & $\{q_0\}$ & $\{q_0,q_2\}$ & $\{q_1\}$ \\
\hline
$q_1$ & $\{q_5\}$ & $\{q_2\}$ & - \\
\hline
$q_2$ & $\{q_3\}$ & - & - \\
\hline
$q_3$ & - & - & $\{q_4\}$ \\
\hline
$q_4$ & $\{q_3\}$ & - & - \\
\hline
$q_5$ & - & $\{q_4\}$ & - \\
\hline
\end{tabular}
\end{center}

{\bf Now do only two of the following three:}

\item Prove that every NFA can be converted to an equivalent one that has a single accepting 
state.

\item Show that $L=\{\epsilon, 0\}$ can' be accepted by an NFA $N$ unless at least one 
of the following conditions is met:

\begin{enumerate}

\item $N$ contains a transition labeled by $\epsilon$.

\item $N$ has at least two accepting states.

\end{enumerate}

\item Prove that if $L$ is a regular language, then $\{x^R ~|~ x \in L\}$ is also regular.

\end{enumerate}

{\bf Note:} Next homework is on minimizing DFA.


\end{document}
