%% 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{blue}Quiz 1}}
\end{center}
{\bf Instructions:} 
Show your work and explain every step. 


\begin{enumerate}

\item Give the mathematical definition of DFA.

\vspace{.5 in}

\item Give the mathematical definition of NFA.

\vspace{.5 in}

\item Given that $L$ is a regular language recognized by the DFA $M=(Q,\Sigma,\delta,q_0,F)$. Give the 5-tuple of a DFA 
(write its elements in terms of the elements of $M$) that recognizes $\overline{L}$. Also, show by example that the above 
does not work for NFA.

\vspace{1 in}

\item Use the above question (i.e. the complement of a regular language is regular) and the fact that the union 
of two regular languages is regular to prove that if $L_1$ and $L_2$ are regular, then 
$L_1 \cap L_2$ is regular. 

\vspace{.5 in}


\item Determine whether the following are true or false:

\begin{enumerate}

\item DFA are as powerful as NFA (i.e. NFA and DFA recognize the same languages).

\item The language $\{ a^n b^n \in \{a,b\}^* ~|~ n \geq 0\}$ is regular.

\end{enumerate}

\newpage 

\item Given the following NFA

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

$F=\{q_3\}$.
\end{center}

\begin{enumerate}
\item Is $\epsilon$ recognized by the NFA?

\vspace{.5 in}

\item What is $\delta(q_0,0)$?

\vspace{.5 in}

\item What is $\delta(q_0,\epsilon)$?

\end{enumerate}

\end{enumerate}
\end{document}