\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Prova} \hfill 28/11/96
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos.
 \item[Valores das quest\~{o}es:] 3 pontos cada uma.
\end{description}
 
\begin{enumerate}
 \item Construa uma m\'aquina de Turing que, recebendo como entrada um n\'umero
       representado em bin\'ario, some 1 ao mesmo e retorne o cabe\c cote de
       leitura para a posi\c c\~ao inicial. Exemplos:
       \begin{itemize}
        \item $q_0 B 1010 B \stackrel{*}{\vdash} q_4 B 1011 B$
        \item $q_0 B 1011 B \stackrel{*}{\vdash} q_4 B 1100 B$
        \item $q_0 B 111 B \stackrel{*}{\vdash} q_4 B 1000 B$
      \end{itemize}
 \item Construa uma m\'aquina de Turing que reconhe\c ca  a linguagem
       \[\{a^nb^{2n} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\]
 \item Construa uma gram\'atica irrestrita que gere a linguagem
       \[\{a^nb^{2n}c^{3n} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\]
 \item Mostre que se uma linguagem $L$ n\~ao \'e recursiva, ent\~ao
       $\overline{L}$ n\~ao \'e recursiva.
 \item Uma computa\c c\~ao de uma m\'aquina de Turing
       $M=(Q,\Sigma,\Gamma,\delta, q_0,F)$ come\c ca sempre no estado inicial
       $q_0$. Prove que n\~ao existe algoritmo que determine se uma m\'aquina de
       Turing arbitr\'aria volta a entrar em seu estado inicial ap\'os iniciar a
       computa\c c\~ao no mesmo, quando iniciada com a fita em branco.
       ({\it Sugest\~ao\/:} reduza o problema da fita em branco a este.) 
 \item D\^e um exemplo de problema indecid\'{\i}vel no contexto de gram\'aticas
       livres do contexto, e prove que o mesmo \'e indecid\'{\i}vel.
 
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
