\documentclass[12pt]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

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

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

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

 \item Construa o diagrama de estados de uma MT padr\~ao que, recebendo
       como entrada uma palavra da forma ${\tt 0}^n$, para $n\geq 0$,
       escreva no lugar da mesma a palavra ${\tt 0}^{2n}$ e, em seguida,
       retorne o cabe\c cote para o in\'{\i}cio da palavra ${\tt 0}^{2n}$.

 \item Construa o diagrama de estados de uma MT n\~ao determin\'{\i}stica
       que reconhe\c ca:\footnote{$n_s(w)$ \'e o n\'umero de
       s\'{\i}mbolos $s$ na palavra $w$.}
       \[\{xy \,\,|\,\,  |x|\geq 1 \mbox{ e } |x|=|y| \mbox{ e } n_0(x)=
         n_1(y)\}\mbox{.}\]
       Fa\c ca de tal forma que a MT d\^e uma \'unica passada sobre a
       palavra de entrada. {\em Dica: use 2 fitas, al\'em da fita de
       entrada, uma para conter o n\'umero de {\tt 0}'s em $x$ e outra
       para conter o n\'umero de {\tt 1}'s em $x$.}

 \item Mostre que toda linguagem recursivamente enumer\'avel pode ser
       reconhecida por uma MT com um \'unico estado final.

 \item Construa uma gram\'atica irrestrita que gere a linguagem
       \[\{x\overline{x}\,\,|\,\,x\in\{{\tt 0},{\tt 1}\}^*\}\mbox{.}\]
       ( $\overline{x}$ \'e o resultado de substituir em $x$ todo {\tt 0}
       por {\tt 1} e todo {\tt 1} por {\tt 0}.)

 \item Sejam $L_1$ e $L_2$ linguagens recursivamente enumer\'aveis, e $R$ uma linguagem recursiva.
       Para cada caso abaixo, diga se a linguagem resultante \'e LRE (recursivamente enumer\'avel),
       NLRE (n\~ao recursivamente enumer\'avel), ou NDA (nenhuma das duas anteriores: \`as vezes \'e
       LRE e \`as vezes n\~ao \'e LRE). Justifique as respostas.
       \begin{enumerate}
        \item[(a)] $L_1-R$
        \item[(b)] $R-L_1$
        \item[(c)] $L_1-L_2$
       \end{enumerate}
\end{enumerate}

\end{document}

