\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
                            $1^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Terceira Prova} 5/9/2002 \hfill {\bf Dura\c c\~ao: 1h:40m}

\vspace*{2mm}
\noindent {\bf Escolha 5 quest\~oes. Cada uma vale 3 pontos.}

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

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

 \item Construa um APN que reconhe\c ca $\{\verb+a+^m\verb+b+^n
        \,\,|\,\, 2m<n<3m\}$.

 \item Construa GLC's que gerem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A=\{\verb+0+^n\verb+1+^k\,\,|\,\, n>2k\}$.
        \item $B=\{\verb+a+^n\verb+b+^k\verb+c+^m\,\,|\,\, k>m+n\}$.
        \item $(A B)^*$.
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, \verb+a+ P \,|\, P \verb+b+ \,|\, \verb+a+$
       \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 GLC n\~ao amb\'{\i}g\"ua equivalente a $G$.
       \end{list}

 \item Seja a gram\'atica $H$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, \verb+a+ A \verb+a+ \,\,|\,\, \verb+b+ B \verb+b+ \,\,|\,\,\lambda$
        \item[\ ] $A\,\rightarrow\, C \,|\, \verb+a+$
        \item[\ ] $B\,\rightarrow\, C \,|\, \verb+b+$
        \item[\ ] $C\,\rightarrow\, CDE \,|\, \lambda$
        \item[\ ] $D\,\rightarrow\, A \,\,|\,\, B  \,|\, \verb+ab+$
       \end{enumerate}
       Construa uma GLC $H'$ sem vari\'aveis in\'uteis, sem regras $\lambda$ e sem
       regras de cadeias tal que $L(H')=L(H)-\{\lambda\}$.

 \item Prove que a linguagem $\{ww\,\,|\,\, w\in\{\verb+a+,\verb+b+\}^*\}$ n\~ao \'e livre do contexto.

\end{enumerate}

\end{document}

