\documentstyle[12pt]{article}

\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ICEx/UFMG \\
\noindent {\it Fundamentos da Teoria da Computa\c c\~ao}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova} \hfill 29/06/2000

\vspace*{3mm}
\noindent Cada quest\~ao vale 4 pontos (em 20).

\vspace*{3mm} 
\begin{enumerate}
 \item Prove que as seguintes afirmativas s\~{a}o verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L-F$ \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L-F$ n\~{a}o \'{e} linguagem livre do contexto.
       \end{list}

 \item Construa um diagrama de estados de uma m\'{a}quina de Turing que reconhe\c{c}a a
       linguagem $\{ww \,\,\,|\,\,\, w\in\{a,b\}^*\}$. Pode usar qualquer
       modelo de m\'{a}quina.

 \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 Prove que toda linguagem recursivamente enumer\'avel \'e aceita por uma m\'aquina de
       Turing com um \'unico estado final.
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
