\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 Quarta Prova} \hfill 29/01/2004 \hfill {\bf Dura\c c\~ao: 1h:30m}

\vspace*{2mm}
\noindent {\bf Cada quest\~ao vale 3 pontos.}

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

 \item Construa uma MT que reconhe\c ca a linguagem
       \[\{\verb+a+\}\{\verb+a+,\verb+b+\}^*\]
       \underline{por parada}. Se a MT n\~ao tiver o \underline{menor n\'umero de
       estados poss\'{\i}vel}, ser\'a descontado 1 ponto na quest\~ao.

 \item Construa uma MT n\~ao determin\'{\i}stica de 2 fitas que reconhe\c ca
       \[\{xx^R\;|\;x \in\{\verb+a+,\verb+b+\}^*\}\mbox{.}\]
       Uma computa\c c\~ao que reconhe\c ca uma palavra $w$ dever\'a utilizar
       no m\'aximo $|w|+2$ transi\c c\~oes; caso contr\'ario, ser\'a descontado
       1 ponto na quest\~ao.

 \item Construa uma gram\'atica irrestrita que gere 
       $\{\verb+0+^n\verb+1+^{n+1}\verb+2+^{n+2}\,\,|\,\, n\geq 0\}$. Se a
       gram\'atica n\~ao for sens\'{\i}vel ao contexto, ser\'a descontado
       1 ponto na quest\~ao.

 \item Mostre que toda linguagem recursivamente enumer\'avel pode ser
       re\-co\-nhe\-ci\-da por uma MT com um \'unico estado final.

 \item Se $L$ \'e uma linguagem recursivamente enumer\'avel n\~ao recursiva,
       de que tipo \'e $\overline{L}$? Por que?

\end{enumerate}

\end{document}

