\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 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Segunda Prova} \hfill 15/04/97

\vspace*{2mm}
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos. {\bf Valores das quest\~{o}es:}
  3 pontos cada uma.
\end{description}

\vspace*{1mm}
\begin{enumerate}
 \item Construa gram\'{a}ticas regulares para
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, w$ cont\'{e}m dois ou mais $b$'s e
              termina com $cc\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ tem exatamente 2 $a$'s e
              tem tamanho par}\}$
       \end{list}
 
 \item Construa gram\'{a}ticas livres do contexto para
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^nb^{2n+k}c^{3k} \,\,|\,\, n,k\geq 0\}$
        \item $\{a^mb^nc^k \,\,|\,\, n>m+k\}$
       \end{list}
 
 \item Seja $G$ a seguinte gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSb \,\,\,|\,\,\,
                  aaaSb \,\,\,|\,\,\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'{e} gerada por $G$?
        \item Mostre que $G$ \'{e} amb\'{\i}gua exibindo duas \'{a}rvores de
              deriva\c{c}\~{a}o para o {\em menor string\/} para o qual existam
              duas \'{a}rvores de deriva\c{c}\~{a}o.
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item D\^{e} exemplos de gram\'{a}ticas equivalentes (isto \'{e}, que gerem a mesma
       linguagem), $G_1$, $G_2$ e $G_3$, tais que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O {\em grafo mais \`{a} esquerda\/} de $G_1$ \'{e} \'{a}rvore.
        \item O {\em grafo mais \`{a} esquerda\/} de $G_2$ n\~{a}o \'{e}
              \'{a}rvore e $G_2$ \'{e} amb\'{\i}gua.
        \item O {\em grafo mais \`{a} esquerda\/} de $G_3$ n\~{a}o \'{e}
              \'{a}rvore e $G_2$ n\~{a}o \'{e} amb\'{\i}gua.
       \end{list}
       
 \item Construa uma gram\'{a}tica na forma normal de Chomsky equivalente \`{a}
       seguinte:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, A \,\,\,|\,\,\, B
                  \,\,\,|\,\,\, ABS$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, 
                  \lambda$                                      
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, aBAb \,\,\,|\,\,\, 
                  \lambda$                                      
       \end{enumerate}

 \item Construa uma gram\'{a}tica na Forma Normal de Greibach equivalente \`{a}
       seguinte gra\-m\'{a}\-ti\-ca:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aAd \,\,\,|\,\,\,
                  A \,\,\,|\,\,\, \lambda$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, Bc \,\,\,|\,\,\, c$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, Ac \,\,\,|\,\,\, SS$
       \end{enumerate}

\end{enumerate}

\end{document}
\endinput
\end

                                                                  
