\documentstyle[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
                            $1^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova} 26/9/2002 \hfill {\bf Dura\c c\~ao: 1h:40m}

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

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

 \item Construa uma MT com alfabeto de entrada $\Sigma=\{\verb+a+,\verb+b+\}$ que,
       recebendo uma palavra de entrada $w$, concatene $w^R$ imediatamente \`a sua
       direita, e retorne o cabe\c cote para o in\'{\i}cio de $ww^R$. Por exemplo,
       se a configura\c c\~ao instant\^anea inicial \'e
       $[i,\langle\underline{\verb+a+}\verb+ababb+]$, a configura\c c\~ao final
       deve ser da forma $[e,\langle\underline{\verb+a+}\verb+ababbbbabaa+]$.

 \item Construa uma MT n\~ao determin\'{\i}stica de duas fitas que reconhe\c ca
       $\{x\verb+c+x^R \,\,|\,\, x\in\{\verb+a+,\verb+b+,\verb+c+\}^*\}$. Uma
       computa\c c\~ao com entrada $w$ deve terminar ap\'os, no m\'aximo, $|w|+1$
       transi\c c\~oes.

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

 \item Construa uma gram\'atica sens\'{\i}vel ao contexto que gere a linguagem
       $\{\verb+a+^n\verb+b+^{2n}\verb+c+^{3n}\,\,|\,\,n>0\}$.

 \item Sejam $L_1$ e $L_2$ linguagens recursivamente enumer\'aveis. Explique
       como poderia ser constru\'{\i}da uma MT para reconhecer $L_1L_2$.
       Podem ser usadas v\'arias fitas, n\~ao determinismo, etc.
\end{enumerate}

\end{document}

