\documentclass{article}
\usepackage{epsfig}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% General formatting parameters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\parskip=.080in
\setlength{\evensidemargin}{0.in}
\setlength{\oddsidemargin}{0.in}
\setlength{\textwidth}{6.612in}
\setlength{\topmargin}{0.in}
\setlength{\textheight}{8.8in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\topsep}{0in}
\setlength{\itemsep}{0in}
\renewcommand{\baselinestretch}{1.2}
\newcommand{\smallsection}[1]{{\smallskip\bf #1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Non-mathematical macros %%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\larry}{{$\calL^3$}}
\newcommand{\marek}{\mbox{${\cal M}\!{\cal C}\!h$}}
\newcommand{\ie}{{\em i.e.}}
\newcommand{\etal}{\mbox{\em et al.\/} }
\newcommand{\tH}{{\rm th}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\etc}{{\em etc.}}
\newcommand{\case}[1]{{\smallskip\noindent{\bf Case #1:\/}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Caligraphic letters %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calJ}{{\cal J}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calQ}{{\cal Q}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calV}{{\cal V}}
\newcommand{\calW}{{\cal W}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calY}{{\cal Y}}
\newcommand{\calZ}{{\cal Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Delimiters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\angled}[1]{{\left\langle #1\right\rangle}}
\newcommand{\barred}[1]{{\left|#1\right|}}
\newcommand{\braced}[1]{{\left\{#1\right\}}}
\newcommand{\brackd}[1]{{\left[#1\right]}}
\newcommand{\parend}[1]{{\left(#1\right)}}
\newcommand{\spaced}[1]{{\ #1\ }}
\newcommand{\dummydot}{{\/\cdot\/}}
\newcommand{\mytimes}{{\!\times\!}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% something-ed letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\barx}{{\bar{x}}}
\newcommand{\bary}{{\bar{y}}}
\newcommand{\cstar}{{c^\ast}}
\newcommand{\phistar}{{\phi^\ast}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Strategy and problems names %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\adv}{{\it adv}}
\newcommand{\MSS}{{\rm MSS}}
\newcommand{\PRP}[1]{{#1\!-\!\mbox{\rm PRP}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Sets and constants %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Domain}{\mbox{\sf Dom\,}}
\newcommand{\reals}{{\rm I\!R}}
\newcommand{\naturals}{ \mbox{\rm I\hspace{-3pt}N} }
\newcommand{\Det}{{\mbox{\sf Det}}}
\newcommand{\distrib}{{\rm I\!D}}
\newcommand{\half}{{\scriptstyle{1\over 2}}}
\newcommand{\Rand}{{\mbox{\sf Rand}}}
\newcommand{\nats}{{\rm I\!N}}
\newcommand{\posreals}{{\rm I\!R^+}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Functions and Operators %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\becomes}{\mbox{$:=$}}
\newcommand{\bdistrib}{{\rm I\!B}}
\newcommand{\cost}{\mbox{\it cost\/}}
\newcommand{\To}{{\Rightarrow}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{observation}{Observation}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{fact}{Fact}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}
\newenvironment{example}[1]{{%
\vskip 0.1in \noindent
{\bf Example~{#1}:\ }%
}}%
{$\Diamond$\vskip 0.1in}
\newenvironment{claim}[1]%
{{\vskip 0.1in\noindent \bf Claim~#1:\ }}%
{\vskip 0.1in}

\newcommand{\sfparagraph}[1]%
{\vskip 0.1in\noindent{\sf #1}}

\newenvironment{mydescription}%
{%
\begin{list}{}%
{%
\setlength{\topsep}{0pt}%
\setlength{\parsep}{0pt}%
\setlength{\partopsep}{0pt}%
\setlength{\itemsep}{0pt}%
\setlength{\itemindent}{0pt}%
\setlength{\labelwidth}{0.2in}%
\setlength{\leftmargin}{0.3in}%
\setlength{\rightmargin}{0.3in}%
}%
}%
{\end{list}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\margincomment}[1]%
{{%
\marginpar{{\tiny\begin{minipage}{0.5in}
\begin{flushleft}
{#1}
\end{flushleft}
\end{minipage}
}}
}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% maly %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\maly}[1]{{\scriptscriptstyle#1}}
\newcommand{\malyz}{{\maly{0}}}
\newcommand{\malyone}{{\maly{1}}}
\newcommand{\malytwo}{{\maly{2}}}
\newcommand{\smallX}{{\scriptscriptstyle X}}
\newcommand{\smallY}{{\scriptscriptstyle Y}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%% fill-in blanks %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\u{\_\_}
\def\uu{\u\u}
\def\uuu{\uu\uu}
\def\uuuu{\uuu\uuu}
\def\uuuuu{\uuuu\uuuu}
\def\uuuuuu{\uuuuu\uuuuu}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\points}[1]{{\ [#1 points]\addtocounter{points}{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
%\thispagestyle{empty}
%\setcounter{page}{0}

\newcounter{points}
\newcounter{jump}
\setcounter{points}{-1}

\newcommand{\answer}[1]{{\bf #1}}
%\renewcommand{\answer}[1]{}
\newcommand{\question}[1]{{#1}}
\renewcommand{\question}[1]{}

{\tt 
\input{tempdt}
}

%\noindent
%The entire examination is \ref{numpoints} points.


%  \begin{enumerate}
%        \item\label{truefalse}


T/F/O: Known to be true, Known to be false, or Open.
		\begin{enumerate}
			\item

\question{\uuu}
\answer{F}
Every subset of a regular language is regular.
\vskip 0.1in
			\item
\question{\uuu}
\answer{F}
Let $L$ be the language over $\Sigma = \braced{a,b}$ consisting of all
strings of the form $a^m b^n$, where $m\ge n$.
Then $L$ is a regular language.
\vskip 0.1in
			\item
\question{\uuu}
\answer{T}
The complement of every regular language is regular.
\vskip 0.1in
			\item
\question{\uuu}
\answer{T}
If a language has an context-free grammar, then it is
is accepted by some push-down automaton.
\vskip 0.1in
			\item
\answer{F}
\question{\uuu}
If a language has an ambiguous context-free grammar, then it is
is not accepted by any deterministic push-down automaton.
\vskip 0.1in
			\item
\answer{F}
\question{\uuu}
There is a PDA that accepts all valid C++ programs.
\vskip 0.1in
			\item
\question{\uuu}
\answer{T}
The intersection of any two regular languages is regular.
\vskip 0.1in
			\item
\question{\uuu}
\answer{T}
The language consisting of all base 3 numerals for positive integers
$n$ such that \mbox{$n\ \%\ 7 = 3$} is regular.
\vskip 0.1in
			\item
\question{\uuu}
\answer{F}
The language consisting of all base 5 numerals for prime positive integers
is regular.
\vskip 0.1in
			\item
\question{\uuu}
\answer{F}
The intersection of any two context-free languages is context-free.
\vskip 0.1in

			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
The Kleene closure of every context-free language is context-free.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{F}
If a language has an unambiguous context-free grammar, then it must be
accepted by some deterministic push-down automaton.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{O}
$\calP$-TIME $ = \calN\calP$-TIME.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{F}
If a language is not in the class $\calP$-TIME, then it must be
undecidable.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{F}
The set of all mathematical statements which are provably true is
decidable.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
The set of all mathematical statements which are provably true is
recursively enumerable.
\vskip 0.1in

			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
If a language $L$ is accepted by some NTM, then there is a TM
which accepts $L$.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
The problem of whether a given grammar generates the empty language
is decidable.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{F}
The problem of whether a given grammar generates all strings over
an alphabet $\Sigma$ is decidable.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every language that can be parsed by an LALR parser can be accepted by
some DPDA.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
If a real number $x$ is the solution to a polynomial equation with
integral coefficients, then there must be a TM that runs forever, writing
the decimal digits of $x$.
\vskip 0.1in
			\item\addtocounter{points}{5}
\question{\uuu}
\answer{T}
There exists a polynomial time algorithm which finds the factors of
any positive integer, if the input integer is written in unary
(``caveman") notation.
\vskip 0.1in

		\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The Boolean circuit problem is undecidable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The complement of every recursive language is recursive.
\vskip 0.1in
\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The complement of every recursively enumerable language is recursively
enumerable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every language which is generated by an unrestricted grammar is recursively
enumerable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The question of whether two context-free grammars generate the same
language is undecidable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
There exists some proposition which is true but which has no proof.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The set of all binary numerals for prime numbers is in the class $\calP$.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
If $L_1$ reduces to $L_2$ in polynomial time, and if $L_1$ is $\calN\calP$,
and if $L_2$ is $\calN\calP$-complete, then $L_1$ must be
$\calN\calP$-complete.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
If $L_1$ reduces to $L_2$ in polynomial time, and if $L_2$ is $\calN\calP$,
and if $L_1$ is $\calN\calP$-complete, then $L_2$ must be
$\calN\calP$-complete.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Given any context-free grammar $G$ and any string $w\in L(G)$, there is
always a unique leftmost derivation of $w$ using $G$.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
For any deterministic finite automaton, there is always a unique minimal
non-deterministic finite automaton equivalent to it.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Using multi-processors and other advanced technology, it is possible to
design a machine which decides the halting problem.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The question of whether two regular expressions are equivalent is
decidable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Let $L = \braced{\angled{M}\;|\;M \mbox{\ halts with no input}}$.
Then $L$ is recursively enumerable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The complement of every context-free language is context-free.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{O}
The complement of every $\calN\calP$ language is $\calN\calP$.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The class of context-free languages is a subclass of $\calP$.
\vskip 0.1in

			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
No language which has an ambiguous context-free grammar can be
accepted by a DPDA.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The question of whether a given Turing Machine halts with empty
input is decidable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The class of languages accepted by non-deterministic finite automata
is the same as the class of languages accepted by deterministic finite
automata.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
If $L_1$ reduces to $L_2$ in polynomial time,
$L_1$ is  $\calN\calP$, then $L_2$ must be $\calN\calP$.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
If $L_1$ reduces to $L_2$ in polynomial time,
$L_2$ is  $\calN\calP$, then $L_1$ must be $\calN\calP$.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Let $F(0) = 1$, and let $F(n) = 2^{F(n-1)}$ for $n > 0$.
Then $F$ is Turing-computable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every language which is accepted by some non-deterministic machine is
accepted by some deterministic machine.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The language of all regular expressions over the binary alphabet is
a regular language.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Let $\pi$ be the ratio of the circumference of a circle to its diameter.
(That's the usual meaning of $\pi$ you learned in second grade.)
The problem of whether the $n^\tH$ digit of $\pi$, for a given $n$,
is equal to a given digit is decidable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
There cannot exist any computer program that can decide whether any two
C++ programs are equivalent.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
An undecidable language is necessarily $\calN\calP$-complete.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every context-free language is in the class $\calP${\sc-time}.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Every function that can be mathematically defined is Turing computable.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The language of all binary strings which are the binary numerals for
prime numbers is context-free.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Every bounded function from integers to integers is Turing-computable.
(We say that $f$ is {\em bounded\/} if there is some $B$ such that
$\barred{f(n)} \le B$ for all $n$.)
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The language of all palindromes over $\braced{0,1}$ is inherently ambiguous.
\vskip 0.1in
			\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Every context-free grammar can be parsed by some deterministic top-down parser.
\vskip 0.1in

\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every context-free grammar can be parsed by some non-deterministic
top-down parser.
\vskip 0.1in

\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Every context-free grammar can be parsed by some deterministic
bottom-up parser.
\vskip 0.1in

\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
Every context-free grammar can be parsed by some non-deterministic
bottom-up parser.
\vskip 0.1in

\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
Commercially available parsers cannot use the LALR technique, since
most modern programming languages are not context-free.
\vskip 0.1in
\item \addtocounter{points}{5}
\question{\uuu}
\answer{F}
The Boolean satisfiability problem is undecidable.
\vskip 0.1in
\item \addtocounter{points}{5}
\question{\uuu}
\answer{O}
There is a parallel processor machine which can solve the boolean circuit
problem in polylogarithmic time.
\vskip 0.1in
\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The set of all binary numerals for prime numbers is in the class
$\calP$-{\sc time}.
\vskip 0.1in
\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
If $\calP=\calN\calP$, then RSA coding is insecure.
\vskip 0.1in

\item \addtocounter{points}{5}
\question{\uuu}
\answer{T}
The Boolean satisfiability problem is $\calN\calP$-complete.
\vskip 0.1in


\item
Fill in the blanks.

\begin{enumerate}

\item
Name two classes of machines that accept the class of regular languages.
\question{\uuuuu}
\answer{DFAs}
\vskip 0.1in
and \question{\uuuuu}\answer{NFAs}.

\item
Name one class of machines that accepts the class of context-free languages.
\question{\uuuuu}\answer{PDAs}.
\vskip 0.1in

\item
If a machine $M$ is \question{\uuuuu}\answer{deterministic},
there is at most one legal move $M$ can make from any give configuration.
\vskip 0.1in


\item\addtocounter{points}{5}
An LALR parser outputs a derivation of its input string which corresponds
to the \question{\uuuuu}\answer{postorder}
visitation of the internal nodes of its parse tree.
\vskip 0.1in

\item\addtocounter{points}{5}
If every string generated by a grammar $G$ has a unique leftmost derivation
using $G$, then we say that $G$ is
\question{\uuuuu}\answer{unambiguous}.
\vskip 0.1in

\item\addtocounter{points}{5}
We are able to prove that every language accepted by an NTM is accepted
by a TM.  In this proof, we construct a TM that emulates the NTM using
a bitstring which we call a \question{\uuuu}\answer{guide} string.
\vskip 0.1in

	\end{enumerate}


\item\label{prob: nfa to dfa}\points{30}
Consider the NFA whose transition diagram is drawn below,
where the input alphabet is $\braced{a,b,c}$.
Draw the transition diagram of an equivalent minimal DFA.
Show your steps.

\vskip 0.5in

\begin{figure}[h!] \begin{center}
\question{
{\epsfig{file=nfa8.eps, width= 3.2in}}
\caption{Find a minimal DFA equivalent to this NFA}
}
\answer{
{\epsfig{file=dfa8.eps, width= 3.2in}}
\caption{Minimal DFA equivalent to the NFA}
}
\end{center} \end{figure}

\item Suppose a machine $M_1$ accepts a language $L$.
Prove that there is some machine $M_2$ which enumerates $L$.

\end{enumerate}

\end{document}
