\documentclass[12pt]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao \hfill ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill
                            $2^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Terceira Prova/Especial} \hfill {\bf Dura\c c\~ao: 1h:30m}

\vspace*{2mm}
\noindent {\bf Cada uma vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}

 \item Construa um APD que reconhe\c ca $\{\verb+a+^n\verb+b+^n \,\,|\,\, n\geq 0\}$
       $\{\verb+a+^n\verb+b+^n \,\,|\,\, n\geq 0\}$.

 \item Construa um APN que reconhe\c ca $\{\verb+a+^n\verb+b+^n\verb+a+^k \,\,|\,\, n,k\geq 0\}$

 \item Construa uma GLC que gere 
       $\{\verb+0+^m\verb+1+^n\verb+2+^k\,\,|\,\, m+n<k\}$.

 \item Seja a gram\'atica $G$:
       \begin{enumerate}
        \item[\ ] $R\,\rightarrow\,  P \,|\, Q \,|\, PQ$
        \item[\ ] $P\,\rightarrow\, \verb+a+ P \verb+b+ \,|\, \lambda$
        \item[\ ] $Q\,\rightarrow\, \verb+b+ Q \verb+a+ \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada por $G$?
        \item Mostre que $G$ \'e amb\'{\i}g\"ua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}g\"ua equivalente a $G$.
       \end{list}

 \item A partir da gram\'atica $G$ da quest\~ao anterior, construa uma gram\'atica
       equivalente na Forma Normal de Chomsky (siga exatamente os passos vistos no curso).

\end{enumerate}

\end{document}

