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

\usepackage{fullpage}
 
\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 1993
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Prova Suplementar}
 
\vspace*{3mm}
\noindent Escolha 5 dentre as seguintes quest\~oes:
 
\begin{enumerate}
 
 \item Seja a linguagem $L=\{w \in \{0,1\}^* \,\,|\,\, \mbox{o terceiro
       s\'{\i}mbolo da direita para a esquerda \'e $1$}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um aut\^omato finito n\~ao determin\'{\i}stico que
	      reconhe\c{c}a $L$.
        \item Construa uma gram\'atica regular que gere $L$.
       \end{list}
 
 \item Seja a gram\'atica
       \begin{enumerate}
        \item[\ \ \ ] $G$: $E \rightarrow E + E \,\,|\,\, E * E \,\,|\,\, a$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
	\item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}
 
 \item Seja a gram\'atica $G$ da quest\~ao anterior
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
	\item Construa uma gram\'atica na forma normal de Greibach equivalente
	      a $G$.
	\item Construa uma express\~ao regular que denote $L(G)$.
       \end{list}
 
 \item Seja a gram\'atica
       \begin{enumerate}
        \item[\ \ \ ] $H$: $S \rightarrow S + S \,\,|\,\, S * S \,\,|\,\,
	                   ( S ) \,\,|\,\, a$
       \end{enumerate}
       Prove que $L(H)$ n\~ao \'e regular.
 
 \item Especifique uma m\'aquina de Turing determin\'{\i}stica de 3 fitas
       que reconhe\c{c}a a linguagem $L=\{ww^Rw \,\,|\,\, w \in \{a,b\}^*\}$.
       N\~ao \'e necess\'ario construir a m\'aquina; basta especific\'a-la
       com precis\~ao e clareza.
 
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
 
        \item Utilizando redu\c{c}\~ao de um problema a outro, como \'e que se
	      prova que um problema \'e:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
	       \item decid\'{\i}vel;
	       \item indecid\'{\i}vel?
	      \end{list}
        \item Que caracter\'{\i}sticas deve ter a linguagem de
	      representa\c{c}\~ao de um problema para que ele seja:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
	       \item decid\'{\i}vel;
	       \item indecid\'{\i}vel?
	      \end{list}
       \end{list}
 
 
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
