\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{1}^{\mbox{\underline{o}}}$ semestre de 1995
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Segunda Prova} \hfill 09/05/95
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 30 minutos.
 \item[Valores das quest\~{o}es:] 5 pontos cada uma.
\end{description}
 
\begin{enumerate}
 \item Seja a gram\'{a}tica $G_1$:
 
       \hspace*{1cm} $S \rightarrow A a S b B \,\,|\,\, \lambda$ \\
       \hspace*{1cm} $A \rightarrow a A \,\,|\,\, a$ \\
       \hspace*{1cm} $B \rightarrow b B \,\,|\,\, \lambda$
 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Defina $L(G_1)$ utilizando nota\c{c}\~{a}o de conjunto.
	\item Mostre que $G_1$ \'{e} amb\'{\i}gua.
	\item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a
	      $G_1$.
       \end{list}
 
 \item Seja a linguagem $L=\{a^mb^n \,\,|\,\, m,n\geq 0 \mbox{ e } m\not= n\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'{a}tica, $G_2$, que gere $L$.
        \item Obtenha uma gram\'{a}tica na forma normal de Chomsky equivalente a
	      $G_2$.
       \end{list}
 
 
 \item Seja a gram\'{a}tica $G_3=(\{E,T,F\},\{+,*,(,),a\},P,E)$, em que $P$
       \'{e} constitu\'{\i}do das regras:
 
       \hspace*{1cm} $E \rightarrow E + T \,\,|\,\, T$ \\
       \hspace*{1cm} $T \rightarrow T + F \,\,|\,\, F$ \\
       \hspace*{1cm} $F \rightarrow ( E ) \,\,|\,\, a$
 
       Obtenha uma gram\'{a}tica na forma normal de Greibach equivalente a
       $G_3$.
 
 \item Seja a linguagem $L=\{w \in \{a,b\}^* \,\,|\,\, w$ cont\'{e}m
       no m\'{\i}nimo 3 s\'{\i}mbolos, e o pen\'{u}ltimo s\'{\i}mbolo de $w$
       tem uma ocorr\^{e}ncia anterior$\}$. Por exemplo: $aab$, $abaa$,
       $ababa$ pertencem a $L$; $\lambda$, $a$, $bb$, $aba$, $bbab$ n\~{a}o
       pertencem a $L$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um aut\^{o}mato finito n\~{a}o determin\'{\i}stico que
	      reconhe\c{c}a $L$.
        \item Construa um aut\^{o}mato finito determin\'{\i}stico que
	      reconhe\c{c}a $L$.
       \end{list}
 
 \item Construa uma express\~{a}o regular que denote a linguagem reconhecida
       pelo aut\^{o}mato finito determin\'{\i}stico, $M$, definido abaixo,
       utilizando o m\'{e}todo do grafo de express\~{o}es:
 
       \hspace*{1cm} $M=(\{q_0,q_1,q_2,q_3\},\{a,b,c\},\delta,q_0,\{q_2,q_3\})$,
       sendo $\delta$ dada por:
 
       \hspace*{2cm} \begin{tabular}{c|ccc}
        $\delta$ & a & b & c\\ \hline
	$q_0$ & $q_1$ & $q_0$ & $q_0$\\
	$q_1$ & $q_1$ & $q_2$ & $q_0$\\
	$q_2$ & $q_3$ & $q_2$ & $q_2$\\
	$q_3$ & $q_3$ & $q_0$ & $q_2$
       \end{tabular}
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 