\documentclass[12pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} \hfill 28/06/2005

\vspace*{1mm}

\noindent {\bf Cada quest\~ao vale 3 pontos.}

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

 \item Construa o diagrama de estados de uma MT que, recebendo
       como entrada uma palavra $w\in\{{\tt 0}, {\tt 1}\}^*$,
       escreva logo em seguida a palavra $w^R$. Assim, se a fita
       que cont\'em a entrada tinha $\langle w\sqcup\ldots$,
       passa a ter $\langle ww^R\sqcup\ldots$.

 \item Construa o diagrama de estados de uma MT n\~ao determin\'{\i}stica
       de 2 fitas que reconhe\c ca:\footnote{$n_s(w)$ \'e o n\'umero de
       s\'{\i}mbolos $s$ na palavra $w$.}
       \[\{xy\in\{{\tt 0},{\tt 1},{\tt 2}\}^* \,\,|\,\,  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.

 \item Mostre que as seguintes afirma\c c\~oes s\~ao equivalentes:
       \begin{itemize}
        \item a linguagem $L$ \'e aceita por uma MT padr\~ao;
        \item a linguagem $L$ \'e aceita por uma MT que aceita por parada (ou
              seja, uma palavra $w$ \'e aceita pela MT se e somente se
              a MT p\'ara se a entrada \'e $w$).
       \end{itemize}

 \item Construa uma gram\'atica irrestrita que gere a linguagem
       $\{{\tt a}^n{\tt b}^n{\tt a}^{n+1}\,|\,n\geq 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}

