\documentclass[11pt, a4paper]{article}
 
\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
 
\newcounter{conta}
\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 1993
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Prova}
 
\vspace*{3mm}
\noindent Escolha 5 dentre as seguintes quest\~oes:
 
\begin{enumerate}
 
 \item Construa uma gram\'atica irrestrita que gere
       $\{ww \,\,|\,\, w \in \{a,b\}^*\}$.
 
 \item Prove que as linguagens recursivamente enumer\'aveis s\~ao fechadas sob
       as seguintes opera\c{c}\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item uni\~ao;
        \item concatena\c{c}\~ao;
	\item fechamento (estrela de Kleene).
       \end{list}
 
 \item D\^e argumentos convincentes para as seguintes afirma\c{c}\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item se $L$ \'e uma linguagem recursiva, ent\~ao $\overline{L}$ \'e
	      uma linguagem recursiva;
        \item se $L$ e $\overline{L}$ s\~ao linguagens recursivamente
	      enumer\'aveis, ent\~ao $L$ \'e uma linguagem recursiva.
       \end{list}
 
 \item Construa uma m\'aquina de Turing {\em de duas fitas\/} que determine se
       dois {\em strings\/} $u$ e $v$ sobre $\{a,b\}$ s\~ao id\^enticos. Uma
       computa\c{c}\~ao da m\'aquina n\~ao poder\'a requerer mais de
       $3(|u|+1)+1$ transi\c{c}\~oes ($|u|$ \'e o n\'umero de s\'{\i}mbolos
       de $u$).
 
 \item Prove que n\~ao existe algoritmo que, recebendo como entrada uma
       m\'aquina de Turing arbitr\'aria $M=(Q,\Sigma,\Gamma,\delta,q_0)$ e um
       estado (tamb\'em arbitr\'ario) $q_i \in Q$, determine se alguma
       computa\c{c}\~ao de $M$ entra no estado $q_i$.
 
 \item Prove que n\~ao existe algoritmo que determine se o complemento de
       uma linguagem gerada por uma gram\'atica livre do contexto arbitr\'aria
       cont\'em um n\'umero infinito de elementos.
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
