\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Segunda Prova} \hfill 26/09/96

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

\vspace*{3mm}
\begin{enumerate}
 \item Construa gram\'{a}ticas regulares para
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, w$ tem pelo menos um $a$, e
               o primeiro $a$ n\~{a}o \'{e} precedido de nenhum $b\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ n\~ao cont\'em os
              {\it substrings\/} $aa$ nem $bb$}\}$
       \end{list}
 
 \item Construa gram\'{a}ticas livres do contexto para
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^mb^nc^k \,\,|\,\, n>m \mbox{ ou } n>k\}$
        \item $\{a^mb^nc^{2(m+n)} \,\,|\,\, m,n\geq 0\}$
       \end{list}
 
 \item Seja $G$ a seguinte gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSb \,\,\,|\,\,\,
                  aaSb \,\,\,|\,\,\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Defina $L(G)$ usando nota\c{c}\~{a}o de conjunto.
        \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 Que rela\c{c}\~{a}o existe entre {\em grafo mais \`{a} esquerda\/} de uma gram\'{a}tica
       e {\em ambiguidade\/} de gram\'{a}tica?
       
 \item Construa uma gram\'{a}tica essencialmente n\~{a}o contr\'{a}ctil, com um s\'{\i}mbolo de
       partida n\~{a}o recursivo, equivalente \`{a} seguinte gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, BSA \,\,\,|\,\,\, A$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, 
                  \lambda$                                      
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, BbAa \,\,\,|\,\,\, 
                  \lambda$                                      
       \end{enumerate}

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

\end{enumerate}
 
\end{document}
\endinput
\end
 
                                                                    
