\documentclass[12pt, a4paper]{report}
\newcounter{conta}
\pagestyle{empty}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Pontos Extra} \hfill 17/04/02

\vspace*{.5cm}
{\bf $\Rightarrow$ Cada quest\~ao vale 2 pontos extra.}

\begin{enumerate}

 \item Liste todas as classes de linguagens vistas no curso e mostre
       o relacionamento entre elas usando a rela\c c\~ao $\subset$.
       Comece com a classe das linguagens regulares e termine com
       ${\cal P}(\Sigma^*)$.

 \item Descreva a hierarquia de Chomsky, e liste as linguagens e
       aut\^omatos associados a cada classe de gram\'atica.

 \item Prove que o problema da parada \'e indecid\'{\i}vel. Pode
       escolher entre provar para linguagens com comandos {\bf enquanto}
       ou provar para m\'aquinas de Turing.

\end{enumerate}

\end{document}
