\documentclass[12pt]{report}

%\addtolength{\topmargin}{-1cm}
\usepackage[portuguese]{babel}
\usepackage{fullpage}
\addtolength{\textheight}{1cm}

\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 2004 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova} \hfill {\bf Dura\c c\~ao: 1h:30m}\hfill 09/12/2004

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

\vspace*{1mm}

\begin{enumerate}
 \item Construa uma MT com alfabeto de entrada $\{{\tt a},{\tt b}\}$ que entra em
       {\em loop\/} se, e somente se, a palavra de entrada come\c ca com {\tt aa}.
       Que linguagem ela aceita sob o crit\'erio de reconhecimento ``por parada''?

 \item Seja a MT de 2 fitas, n\~ao determin\'{\i}stica,
       $M=(\{i,m,f\},\{{\tt 0}\},\{{\tt 0},\langle,\sqcup\},\langle,\sqcup,\delta,i,
       \{f\})$, sendo $\delta$ dada por:
       \begin{enumerate}
        \item[\ ] $\delta(i,{\tt 0},\sqcup)=\{
                        [i,{\tt 0},{\tt D},\sqcup,{\tt D}],
                        [m,{\tt 0},{\tt I},\sqcup,{\tt E}]\}$
        \item[\ ] $\delta(m,{\tt 0},\sqcup)=
                        [m,{\tt 0},{\tt D},\sqcup,{\tt E}]$
        \item[\ ] $\delta(m,\langle,\langle)=
                        [f,\langle,{\tt D},\langle,{\tt D}]$

       \end{enumerate}
       Que linguagem $M$ reconhece?

 \item Construa uma gram\'atica irrestrita que gere
       $\{xyx^R\in \{{\tt 0},{\tt 1}\}^* \,\,|\,\, |y|=|x|\}$.

 \item Construa uma MT que reconhe\c ca $\{{\tt 0}^{|w|}w \,\,|\,\,
       w\in\{{\tt 0},{\tt 1}\}^*\}$. Use mais de uma fita e n\~ao
       determinismo para propiciar uma passada \'unica na palavra
       de entrada e economizar transi\c c\~oes.

 \item Mostre como construir uma MT que reconhece por parada a partir
       de uma MT que reconhece por parada em estado final.

 \item Mostre que se uma linguagem $L$ \'e recursivamente enumer\'avel e
       n\~ao \'e recursiva, ent\~ao $\overline{L}$ n\~ao \'e recursivamente
       enumer\'avel.
\end{enumerate}

\end{document}
