\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\newcounter{conta3}
\begin{document} \footnotesize
 
\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{Solu\c c\~ao da Quarta Lista de Exerc\'{\i}cios}

\begin{flushleft} \large\bf
 {An\'{a}lise Sint\'{a}tica: Uma Introdu\c{c}\~{a}o}
\end{flushleft}


\begin{enumerate}
 \item {\it Seja $G$ a gram\'{a}tica}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\, Sb
                  \,\,\,|\,\,\, ab \,\,\,|\,\,\, SS$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it D\^{e} uma express\~{a}o regular para $L(G)$.}
        
              {\boldmath $(a^+b^+)^+$}
        
        \item {\it Construa duas deriva\c{c}\~{o}es mais a esquerda de $aabb$.}

              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$aS$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    aS)$ \\
                  &$\Longrightarrow$&$aSb$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    Sb)$ \\
                  &$\Longrightarrow$&$aabb$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    ab)$
              \end{tabular}

              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$Sb$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    Sb)$ \\
                  &$\Longrightarrow$&$aSb$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    aS)$ \\
                  &$\Longrightarrow$&$aabb$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    ab)$
              \end{tabular}

        \item {\it Construa as \'{a}rvores de deriva\c{c}\~{a}o para as
              deriva\c{c}\~{o}es da parte (b).}
              \begin{center}
              \begin{picture}(240,110)
               \put(30,100){\makebox(0,0){$S$}}
               \put(25,95){\line(-1,-1){20}}
               \put(35,95){\line(1,-1){20}}

               \put(0,70){\makebox(0,0){$a$}}
               \put(60,70){\makebox(0,0){$S$}}
               \put(55,65){\line(-1,-1){20}}
               \put(65,65){\line(1,-1){20}}
               
               \put(90,40){\makebox(0,0){$b$}}
               \put(30,40){\makebox(0,0){$S$}}
               \put(25,35){\line(-1,-1){20}}
               \put(35,35){\line(1,-1){20}}
               \put(0,10){\makebox(0,0){$a$}}
               \put(60,10){\makebox(0,0){$b$}}
               

               \put(210,100){\makebox(0,0){$S$}}
               \put(205,95){\line(-1,-1){20}}
               \put(215,95){\line(1,-1){20}}

               \put(240,70){\makebox(0,0){$b$}}
               \put(180,70){\makebox(0,0){$S$}}
               \put(175,65){\line(-1,-1){20}}
               \put(185,65){\line(1,-1){20}}
               
               \put(150,40){\makebox(0,0){$a$}}
               \put(210,40){\makebox(0,0){$S$}}
               \put(205,35){\line(-1,-1){20}}
               \put(215,35){\line(1,-1){20}}
               \put(180,10){\makebox(0,0){$a$}}
               \put(240,10){\makebox(0,0){$b$}}
              \end{picture}
              \end{center}
        \item {\it Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente
              a $G$.}

             \begin{enumerate}
              \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\,
                         abA$
              \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bA \,\,\,|\,\,\,
                         S \,\,\,|\,\,\, \lambda$
            \end{enumerate}

       \end{list}
 \item {\it Seja $G$ a gram\'{a}tica}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AaSbB \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, a$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it Defina $L(G)$ usando nota\c{c}\~{a}o de conjunto.}
        
              $\{a^naabb^k \,\,\,|\,\,\, n,k\geq 0\}\cup \{\lambda\}$
        
        \item {\it Mostre que $G$ \'{e} amb\'{\i}gua.}
        
              Duas deriva\c c\~oes mais a esquerda para o {\it string\/} $aaaabbb$:
        
              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$AaSbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    AaSbB)$ \\
                  &$\Longrightarrow$&$aaSbB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    a)$ \\
                  &$\Longrightarrow$&$aaAaSbBbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    AaSbB)$ \\
                  &$\Longrightarrow$&$aaaaSbBbB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    a)$ \\
                  &$\Longrightarrow$&$aaaabBbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aaaabbB$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aaaabbbB$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    bB)$ \\
                  &$\Longrightarrow$&$aaaabbb$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
              \end{tabular}

              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$AaSbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    AaSbB)$ \\
                  &$\Longrightarrow$&$aaSbB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    a)$ \\
                  &$\Longrightarrow$&$aaAaSbBbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    AaSbB)$ \\
                  &$\Longrightarrow$&$aaaaSbBbB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    a)$ \\
                  &$\Longrightarrow$&$aaaabBbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aaaabbBbB$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    bB)$ \\
                  &$\Longrightarrow$&$aaaabbbB$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aaaabbb$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
              \end{tabular}

        \item {\it Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente
              a $G$.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AabB
                          \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, a$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB
                          \,\,\,|\,\,\, \lambda$
              \end{enumerate}

       \end{list}

 \item {\it Construa duas gram\'{a}ticas, uma amb\'{\i}gua e outra n\~{a}o, que
       gerem a linguagem {\boldmath $a^*$}.}

       Amb\'{\i}gua:
           
        \begin{enumerate}
         \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\,
                    Sa \,\,\,|\,\,\, \lambda$
        \end{enumerate}
        
        N\~ao amb\'{\i}gua:
        
        \begin{enumerate}
         \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\,
                    \lambda$
        \end{enumerate}
    
 \item {\it \'{E} poss\'{\i}vel ter gram\'{a}ticas regulares amb\'{\i}guas? Se
       sim, d\^{e} um exemplo. Se n\~{a}o, prove que n\~{a}o.}

      Sim, \'e poss\'{\i}vel. Por exemplo:
       
      \begin{enumerate}
       \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\,
                  a \,\,\,|\,\,\, \lambda$
      \end{enumerate}

 \item {\it Que rela\c{c}\~{a}o existe entre {\em grafo mais \`{a} esquerda\/}
       de uma gram\'{a}tica (def. 4.2.1 de S88) e {\em ambiguidade\/} de
       gram\'{a}tica?}
       
       
       Se o grafo for uma \'arvore, a gram\'atica n\~ao \'e amb\'{\i}gua. Se o
       grafo n\~ao for uma \'arvore, a gram\'atica \'e necessariamente
       amb\'{\i}gua no caso em que a gram\'atica n\~ao tenha vari\'aveis
       in\'uteis; se a gram\'atica tiver alguma vari\'avel in\'util, a
       gram\'atica pode ser amb\'{\i}gua (no caso em que s\'o vari\'avel
       in\'util \'e "respons\'avel pela quebra" da estrutura de \'arvore) ou
       n\~ao (no caso contr\'ario).
\end{enumerate}

\end{document}
