\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Prova} \hfill 26/6/97
 
\begin{enumerate}
 \item (4 pontos) Construa uma m\'{a}quina de Turing que reconhe\c{c}a a
       linguagem \[\{w\in \{a,b\}^{*} \,\,|\,\, w\not= w^R\}\mbox{,}\] ou seja,
       o conjunto dos {\it strings\/} sobre $\{a,b\}$ que n\~ao s\~ao
       pal\'{\i}ndromos.

 \item (4 pontos) Mostre que as seguintes afirma\c c\~oes s\~ao equivalentes:
       \begin{itemize}
        \item a linguagem $L$ \'e aceita por uma m\'aquina de Turing padr\~ao;
        \item a linguagem $L$ \'e aceita por uma m\'aquina de Turing que aceita
              por parada.
       \end{itemize}

 \item (4 pontos) Construa uma gram\'atica sens\'{\i}vel ao contexto que gere a
       linguagem \[\{a^nb^{2n}a^n \,\,|\,\, n>0\}\mbox{.}\]

 \item (4 pontos) Mostre que se o problema da parada fosse decid\'{\i}vel,
       ent\~ao toda linguagem recursivamente enumer\'avel seria recursiva.

 \item (3 pontos) Mostre que n\~ao existe algoritmo para determinar se $L(G_1)=
       L(G_2)$, para duas gram\'aticas livres do contexto arbitr\'arias $G_1$ e
       $G_2$. ({\it Sugest\~ao\/}: o problema de determinar se $L(G)=\Sigma^*$,
       para uma gram\'atica livre do contexto arbitr\'aria $G$, \'e
       indecid\'{\i}vel; assim, basta reduzir este problema \`aquele.)
 
 \item (1 ponto) Seja a linguagem: \[L = \left\{ \begin{array}{ll}
                     \{1\} & \mbox{se Deus existe} \\
                     \{0\} & \mbox{se Deus n\~ao existe}
                    \end{array}
                   \right. \]
        Existe algoritmo que, dado um {\it string\/} arbitr\'ario
        $w\in\{0,1\}^*$, determine se $w\in L$? Explique.
  
\end{enumerate}
 
\end{document}
\endinput
\end