\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
                            $1^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova} 25/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 que, recebendo como entrada um n\'umero em no\-ta\-\c c\~ao bin\'aria,
       some 1 ao mesmo e retorne o cabe\c cote para o in\'{\i}cio do n\'umero. Assuma
       que a palavra de entrada cont\'em pelo menos um d\'{\i}gito.

 \item Construa uma MT n\~ao determin\'{\i}stica que reconhe\c ca $\{xx
        \,\,|\,\, x\in\{\verb+0+,\verb+1+\}^*\}$.

 \item Mostre que uma linguagem $L$ pode ser reconhecida por uma MT por parada se,
       e somente se, $L$ pode ser reconhecida por uma MT por estado final.

       (Lembrete: Seja uma MT $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$. Ent\~ao:
       \[L_P(M)=\{w\in\Sigma^*\,|\,[i,\langle\underline{w}]\stackrel{*}{\vdash}
                  [e,x\underline{a}y] \mbox{ e } \delta(e,a) \mbox{ \'e indefinido}\}\mbox{,}\]
       e
       \[L_F(M)=\{w\in\Sigma^*\,|\,[i,\langle\underline{w}]\stackrel{*}{\vdash}
                  [e,x\underline{a}y] \mbox{ e } e\in F\}\mbox{.)}\]

 \item Construa uma gram\'atica sens\'{\i}vel ao contexto que gere a linguagem
       $\{x\verb+b+x\,\,|\,\,x\in\{\verb+a+,\verb+c+\}^*\}$.

 \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}

