\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} \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 $\{w\in\{\verb+a+,\verb+b+\}^*
        \,\,|\,\, w$ tem algum prefixo com mais \verb+a+'s que \verb+b+'s$\}$.

 \item Construa um APN que reconhe\c ca $\{x{\tt c}wx^R\;|\;x,w
         \in\{\verb+a+,\verb+b+\}^*\}$.

 \item Construa GLC's que gere 
       $\{\verb+0+^m\verb+1+^n\verb+2+^k\,\,|\,\, n>m \mbox{ ou } n>k\}$.

 \item Seja a gram\'atica $G$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, \verb+a+ P \verb+a+ \,|\, \verb+b+ P \verb+b+
                              \,|\, A$
        \item[\ ] $A\,\rightarrow\, \verb+a+ A  \,|\, A \verb+b+ \,|\, \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.
       \end{list}

 \item Seja a gram\'atica $H$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, A B \verb+c+$
        \item[\ ] $A\,\rightarrow\, B C \,|\, \verb+a+ A$
        \item[\ ] $B\,\rightarrow\, \lambda$
        \item[\ ] $C\,\rightarrow\, A \verb+b+ C \,|\, B$
       \end{enumerate}
       Construa uma GLC $H'$ sem regras $\lambda$, sem
       regras de cadeias e sem vari\'aveis in\'uteis tal que $L(H')=L(H)$.
       Siga exatamente o roteiro proposto no curso com os m\'etodos l\'a
       apresentados.

\end{enumerate}

\end{document}

