%% 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}Exam 1}}
\end{center}

\vspace{.4 in}

{\bf Instructions:} Show your work and explain every step. No explanation or insufficient explanation may result in a partial 
credit or no credit (depending on the situation). Do each question on a separate sheet of paper. Organize your solutions and 
cross out any unwanted work. The exam is closed book and closed notes. The Internet, computers, cell. phones, electronic devices, books, etc, are not allowed. 
No material printed or electronic can be used including graded homework, etc. Also, let me stress that cell. phones are not allowed to use 
at all. No communications with anyone are allowed during the test. 
{\bf Time: } 50 minutes.

\vspace{.4 in}

\begin{enumerate}

\item (22 points) Construct a STD for a PDA that recognizes the language $\{a^i 
b^{j}~|~ i, j \geq 0, ~ 3i > 4 j\}$. The only transitions I'm allowing you to use are of the form 

$a,\epsilon \longrightarrow a$, 

$\epsilon,\epsilon \longrightarrow a$, 

$\epsilon,\epsilon \longrightarrow \epsilon$, 

$b,a \longrightarrow \epsilon$, 

$\epsilon,a \longrightarrow \epsilon$.

\item (22 points) Minimize (i.e. find an equivalent DFA with the least possible number 
of states) the following DFA $M=(Q,\Sigma,\delta,q_0,F)$ using the algorithm we covered in class (if you use 
any other method, you'll get no credit), where 
$Q=\{q_0,q_1,q_2,q_3,q_4\}$, $F=\{q_1,q_4\}$, $\Sigma=\{a,b\}$, 
and $\delta$ is given by

\begin{center}
\begin{tabular}{|c|c|c|}
\hline \\
$\delta$ &  a & b\\
\hline
$q_0$ & $q_0$ & $q_1$ \\
\hline
$q_1$ & $q_2$ & $q_1$ \\
\hline
$q_2$ & $q_3$ & $q_4$ \\
\hline
$q_3$ & $q_4$ & $q_1$ \\
\hline
$q_4$ & $q_4$ & $q_0$ \\
\hline
\end{tabular}
\end{center}

\item (22 points) Transform the following NFA $N=(Q,\{0,1\},\delta,q_0,F)$ to a DFA 
(it suffices to give the STD of the DFA) using the algorithm we covered in class (if you use 
any other method, you'll get no credit), where 
$Q=\{q_0,q_1, \cdots, q_5\}$, $F=\{q_0\}$, and $\delta$ is as follows:

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

\item (16 points)

\begin{enumerate}

\item Give the formal (mathematical definition) of NFA.

\item What does a configuration of $(q,x,\gamma)$ mean in PDA?


\end{enumerate}

\item (18 points) Determine if the following are true or false:

\begin{enumerate} 

\item DFA is as powerful as NFA.

\item DPDA is as powerful as NPDA.

\item If $L_1$ and $L_2$ are regular languages, then so is $L_1 L_2$.

\item If $L$ is a regular language, then so is $L^R$.

\item The language of the FA that accepts no strings is $\{\epsilon\}$.

\item Every regular language is contest free.

\item $\{a^n b^n ~|~ n \geq 0\}$ is regular.

\item $\{a^n b^n c^n ~|~ n \geq 0\}$ is contest free.

\item The stack alphabet $\Gamma$ and the input alphabet $\Sigma$ in the PDA must be the same.

\end{enumerate}

\end{enumerate}


\end{document}

