\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{Segunda Prova}
 
%\vspace*{3mm}
\begin{enumerate}
 \item Seja a gram\'atica $G_1$:
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $a S b \,\,|\,\, a a S b \,\,|\,\, \lambda$
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G_1$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G_1$.
       \end{list}
 \item Construa uma gram\'atica essencialmente n\~ao contr\'actil equivalente
       \`a seguinte gra\-m\'a\-ti\-ca:
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $B S A \,\,|\,\, A$ \\
        $A$ & $\rightarrow$ & $a A \,\,|\,\, \lambda$ \\
        $B$ & $\rightarrow$ & $B b a \,\,|\,\, \lambda$
       \end{tabular}
       \end{center}
 \item Seja a gram\'atica $G_2$:
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $A \,\,|\,\, C B$ \\
        $A$ & $\rightarrow$ & $C \,\,|\,\, D$ \\
        $B$ & $\rightarrow$ & $b B \,\,|\,\, b$ \\
        $C$ & $\rightarrow$ & $c C \,\,|\,\, c$ \\
        $D$ & $\rightarrow$ & $d D \,\,|\,\, d$ \\
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma gram\'atica equivalente a $G_2$, sem regras de
	      cadeias.
        \item Mostre que a gram\'atica constru\'{\i}da cont\'em s\'{\i}mbolos
	      in\'uteis.
       \end{list}
 \item Construa um aut\^omato finito determin\'{\i}stico que reconhe\c{c}a a
       seguinte linguagem:
       \[ \{ w \in \{a, b\}^* \,\,\,|\,\,\, w \,\,\mbox{cont\'em no m\'aximo
          2 $a$'s e no m\'{\i}nimo 2 $b$'s} \}\mbox{.} \]
 \item Construa um aut\^omato finito determin\'{\i}stico equivalente ao
       seguinte aut\^omato finito n\~ao determin\'{\i}stico:
       \[ (\{q_0, q_1, q_2, q_3\},\{a, b\}, \delta, q_0, \{q_3\})
          \mbox{, sendo $\delta$ dada por:} \]
	\begin{center}
	\begin{tabular}{c|cc}
	 $\delta$ & $a$            & $b$            \\ \hline
         $q_0$    & $\{q_1, q_2\}$ & $\{q_1\}$      \\
         $q_1$    & $\{q_2\}$      & $\{q_3\}$      \\
         $q_2$    & $\{\}$         & $\{q_1, q_3\}$ \\
         $q_3$    & $\{\}$         & $\{\}$
	\end{tabular}
	\end{center}
       Utilize o m\'etodo apresentado no curso.
 \item Construa uma express\~ao regular a partir do aut\^omato finito n\~ao
       determin\'{\i}stico da quest\~ao anterior, utilizando o m\'etodo
       do grafo de express\~oes.
\end{enumerate}
 
\end{document}
\endinput
\end
 
