\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 Terceira Lista de Exerc\'{\i}cios}

\begin{flushleft} \large\bf
 {Gram\'{a}ticas Livres do Contexto}
\end{flushleft}

 
\begin{enumerate}
 \item {\it Seja $G$ a gram\'{a}tica}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, ASB \,\,\,|\,\,\,
                  \lambda$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bBa \,\,\,|\,\,\, ba$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it D\^{e} uma deriva\c{c}\~{a}o mais a esquerda de $aabbba$.}
        
              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$ASB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    ASB)$ \\
                  &$\Longrightarrow$&$aAbSB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    aAb)$ \\
                  &$\Longrightarrow$&$aaAbbSB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    aAb)$ \\
                  &$\Longrightarrow$&$aabbSB$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aabbB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aabbba$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    ba)$
              \end{tabular}
        
        \item {\it D\^{e} uma deriva\c{c}\~{a}o mais a direita de $abaabbbabbaa$.}
        
              \begin{tabular}{ccll}
               $S$&$\Longrightarrow$&$ASB$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    ASB)$ \\
                  &$\Longrightarrow$&$ASbBa$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    bBa)$ \\
                  &$\Longrightarrow$&$ASbbaa$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    ba)$ \\
                  &$\Longrightarrow$&$AASBbbaa$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    ASB)$ \\
                  &$\Longrightarrow$&$AASbabbaa$ & \ \ \ $(B \,\,\,\rightarrow\,\,\, 
                    ba)$ \\
                  &$\Longrightarrow$&$AAbabbaa$ & \ \ \ $(S \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$AaAbbabbaa$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    aAb)$ \\
                  &$\Longrightarrow$&$AaaAbbbabbaa$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    aAb)$ \\
                  &$\Longrightarrow$&$Aaabbbabbaa$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    \lambda)$ \\
                  &$\Longrightarrow$&$aAbaabbbabbaa$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    aAb)$ \\
                  &$\Longrightarrow$&$abaabbbabbaa$ & \ \ \ $(A \,\,\,\rightarrow\,\,\, 
                    \lambda)$
              \end{tabular}
        
        \item {\it Construa as \'{a}rvores de deriva\c{c}\~{a}o para as
              deriva\c{c}\~{o}es das partes (a) e (b).}
            
              A \'arvore de deriva\c c\~ao para a parte (a) \'e:
              \begin{center}
              \begin{picture}(200,140)
               \put(100,130){\makebox(0,0){$S$}}
               \put(95,125){\line(-2,-1){40}}
               \put(100,125){\line(0,-1){20}}
               \put(105,125){\line(2,-1){40}}
               
               \put(50,100){\makebox(0,0){$A$}}
               \put(45,95){\line(-1,-1){20}}
               \put(20,70){\makebox(0,0){$a$}}
               \put(50,95){\line(0,-1){20}}
               \put(50,70){\makebox(0,0){$A$}}
               \put(55,95){\line(1,-1){20}}
               \put(80,70){\makebox(0,0){$b$}}
               
               \put(45,65){\line(-1,-1){20}}
               \put(20,40){\makebox(0,0){$a$}}
               \put(50,65){\line(0,-1){20}}
               \put(50,40){\makebox(0,0){$A$}}
               \put(50,35){\line(0,-1){20}}
               \put(50,10){\makebox(0,0){$\lambda$}}
               \put(80,40){\makebox(0,0){$b$}}
               \put(55,65){\line(1,-1){20}}
               \put(80,40){\makebox(0,0){$b$}}
               
               \put(100,100){\makebox(0,0){$S$}}
               \put(100,95){\line(0,-1){20}}
               \put(100,70){\makebox(0,0){$\lambda$}}

               \put(150,100){\makebox(0,0){$B$}}
               \put(145,95){\line(-1,-1){20}}
               \put(120,70){\makebox(0,0){$b$}}
               \put(155,95){\line(1,-1){20}}
               \put(180,70){\makebox(0,0){$a$}}
              \end{picture}
              \end{center}
              A \'arvore da parte (b) \'e constru\'{\i}da de forma an\'aloga.
                    
        \item {\it Use nota\c{c}\~{a}o de conjunto para definir $L(G)$.}
              \[L(G)=\bigcup_{n\geq 0}\{a^ib^i\,\,\,|\,\,\, i\geq 0\}^n
                      \{b^ja^j\,\,\,|\,\,\, j\geq 1\}^n\].
        
       \end{list}
 \item {\it Seja {\em AD\/} a \'{a}rvore de deriva\c{c}\~{a}o}
       \begin{center}
       \begin{picture}(200,180)
        \put(100,167){\makebox(0,0)[b]{$S$}}
        \put(100,165){\line(-3,-2){60}}
        \put(100,165){\line(3,-2){60}}

        \put(40,112){\makebox(0,0)[b]{$A$}}
        \put(40,110){\line(-1,-1){40}}
        \put(40,110){\line(1,-1){40}}

        \put(160,112){\makebox(0,0)[b]{$B$}}
        \put(160,110){\line(-1,-1){40}}
        \put(160,110){\line(1,-1){40}}

        \put(0,66){\makebox(0,0)[t]{$a$}}

        \put(80,57){\makebox(0,0)[b]{$A$}}
        \put(80,55){\line(0,-1){40}}
        \put(80,11){\makebox(0,0)[t]{$a$}}

        \put(120,57){\makebox(0,0)[b]{$A$}}
        \put(120,55){\line(0,-1){40}}
        \put(120,11){\makebox(0,0)[t]{$a$}}

        \put(200,57){\makebox(0,0)[b]{$B$}}
        \put(200,55){\line(0,-1){40}}
        \put(200,13){\makebox(0,0)[t]{$b$}}
       \end{picture}
       \end{center}       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it D\^{e} uma deriva\c{c}\~{a}o mais a esquerda que gere a
              \'{a}rvore {\em AD\/}.}
        
              $S\Longrightarrow AB\Longrightarrow aAB\Longrightarrow aaB
                \Longrightarrow aaAB\Longrightarrow aaaB\Longrightarrow aaab$
        
        \item {\it D\^{e} uma deriva\c{c}\~{a}o mais a direita que gere a
              \'{a}rvore {\em AD\/}.}

              $S\Longrightarrow AB\Longrightarrow AAB\Longrightarrow AAb
                \Longrightarrow Aab\Longrightarrow aAab\Longrightarrow aaab$
              
        \item {\it Quantas deriva\c{c}\~{o}es diferentes geram {\em AD\/}?}
        
               S\~ao 20. Uma forma de determinar este n\'umero, \'e contar o
               n\'umero de caminhos de $S$ a $aaab$ no grafo dirigido de todas
               as deriva\c c\~oes poss\'{\i}veis (v\'ertices: formas sentenciais
               obten\'{\i}veis; arestas: pares $[u,v]$ tais que
               $u\Longrightarrow v$).
        
       \end{list}
 \item {\it Construa uma gram\'{a}tica regular para cada uma das linguagens do 
       exerc\'{\i}cio 2.7.}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ que n\~{a}o
              cont\^{e}m $aa$.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, bS \,\,\,|\,\,\, cS
                          \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bS
                          \,\,\,|\,\,\, cS \,\,\,|\,\,\, \lambda$                                      
              \end{enumerate}

        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ nos quais
              cada $b$ \'{e} seguido por pelo menos um $c$.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS
                          \,\,\,|\,\,\, bA \,\,\,|\,\,\, cS
                          \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, cS$                                      
              \end{enumerate}

        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o
              n\'{u}mero de $a$'s \'{e} divis\'{\i}vel por 3.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, bS \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aB
                          \,\,\,|\,\,\, bA$                                      
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, aS
                          \,\,\,|\,\,\, bB$                                      
              \end{enumerate}

        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              $a$ \'{e} precedido (imediatamente) ou seguido (imediatamente) por
              $b$.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, bB \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bB$                                      
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, aS
                          \,\,\,|\,\,\, bB \,\,\,|\,\,\, \lambda$                                      
              \end{enumerate}

        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ com n\'{u}mero
              par de $a$'s e n\'{u}mero par de $b$'s.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$\langle pp\rangle
                          \,\,\,\rightarrow\,\,\, a\langle ip\rangle
                          \,\,\,|\,\,\, b\langle pi\rangle$
               \item[\ ] \hspace*{1cm}$\langle ip\rangle
                          \,\,\,\rightarrow\,\,\, a\langle pp\rangle
                          \,\,\,|\,\,\, b\langle ii\rangle$
               \item[\ ] \hspace*{1cm}$\langle pi\rangle
                          \,\,\,\rightarrow\,\,\, a\langle ii\rangle
                          \,\,\,|\,\,\, b\langle pp\rangle$
               \item[\ ] \hspace*{1cm}$\langle ii\rangle
                          \,\,\,\rightarrow\,\,\, a\langle pi\rangle
                          \,\,\,|\,\,\, b\langle ip\rangle$
              \end{enumerate}

        \item {\it o conjunto dos {\em strings\/} de tamanho \'{\i}mpar sobre
              $\{a,b\}$ que cont\^{e}m exatamente dois $b$'s.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$\langle p0\rangle
                          \,\,\,\rightarrow\,\,\, a\langle i0\rangle
                          \,\,\,|\,\,\, b\langle i1\rangle$
               \item[\ ] \hspace*{1cm}$\langle p1\rangle
                          \,\,\,\rightarrow\,\,\, a\langle i1\rangle
                          \,\,\,|\,\,\, b\langle i2\rangle$
               \item[\ ] \hspace*{1cm}$\langle p2\rangle
                          \,\,\,\rightarrow\,\,\, a\langle i2\rangle$
               \item[\ ] \hspace*{1cm}$\langle i0\rangle
                          \,\,\,\rightarrow\,\,\, a\langle p0\rangle
                          \,\,\,|\,\,\, b\langle p1\rangle$
               \item[\ ] \hspace*{1cm}$\langle i1\rangle
                          \,\,\,\rightarrow\,\,\, a\langle p1\rangle
                          \,\,\,|\,\,\, b\langle p2\rangle$
               \item[\ ] \hspace*{1cm}$\langle i2\rangle
                          \,\,\,\rightarrow\,\,\, a\langle p2\rangle
                          \,\,\,|\,\,\, \lambda$
             \end{enumerate}

       \end{list}

       
 \item {\it Construa uma gram\'{a}tica para cada uma das linguagens:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^mb^n \,\,\,|\,\,\, m>n\}$.
        
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS
                          \,\,\,|\,\,\, aA$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aAb
                          \,\,\,|\,\,\, \lambda$                                      
              \end{enumerate}

        \item $\{w\in\{a,b\}^* \,\,\,|\,\,\, \mbox{o n\'{u}mero de $a$'s em $w$ \'{e} o
              dobro do n\'{u}mero de $b$'s}\}$.
        
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSaSbS
                          \,\,\,|\,\,\, aSbSaS \,\,\,|\,\,\, bSaSaS
                          \,\,\,|\,\,\, \lambda$

              \end{enumerate}

        \item $\{a^mb^n \,\,\,|\,\,\, n\leq m \leq 2n\}$.
        
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSb
                          \,\,\,|\,\,\, aaSb \,\,\,|\,\,\, \lambda$                                      
              \end{enumerate}

        \item $\{a^mb^nc^pd^q \,\,\,|\,\,\, m+n \geq p+q\}$.
        
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSd
                          \,\,\,|\,\,\, A \,\,\,|\,\,\, B$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bAd
                          \,\,\,|\,\,\, C$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, aBc
                          \,\,\,|\,\,\, C \,\,\,|\,\,\, D$                                      
               \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, bCc
                          \,\,\,|\,\,\, E$
               \item[\ ] \hspace*{1cm}$D \,\,\,\rightarrow\,\,\, aD
                          \,\,\,|\,\,\, E$
               \item[\ ] \hspace*{1cm}$E \,\,\,\rightarrow\,\,\, bE
                          \,\,\,|\,\,\, \lambda$
             \end{enumerate}
             A seguinte tabela mostra que {\it strings\/} s\~ao gerados a partir
             de cada vari\'avel:
             \begin{center}
             \begin{tabular}{cl}
              {\it Vari\'avel} & {\it Strings} \\ \hline
              S & $\{a^mb^nc^pd^q \,\,\,|\,\,\, m+n \geq p+q\}$ \\
              A & $\{b^nc^pd^q \,\,\,|\,\,\, n \geq p+q\}$ \\
              B & $\{a^mb^nc^p \,\,\,|\,\,\, m+n \geq p\}$ \\
              C & $\{b^nc^p \,\,\,|\,\,\, n \geq p\}$ \\
              D & $\{a^mb^n \,\,\,|\,\,\, m+n \geq 0\}$ \\
              E & $\{b^n \,\,\,|\,\,\, n \geq 0\}$ \\
             \end{tabular}
             \end{center}

       \end{list}
 \item {\it Seja $G$ a gram\'{a}tica}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSaa \,\,\,|\,\,\, B$ 
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbBdd \,\,\,|\,\,\, C$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, bd$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it O que \'{e} $L(G)$?}
        
              $X=\{a^nb^{2k+1}d^{2k+1}a^{2n} \,\,\,|\,\,\, n,k \geq 0\}$
        
        \item {\it Prove que $L(G)$ \'{e} o conjunto dado em (a).}
        
              \begin{list}{(\arabic{conta2})}{\usecounter{conta2}}
               \item $X\subseteq L(G)$
               
                     \begin{tabular}{cclcl}
                      $S$&$\stackrel{n}{\Longrightarrow}$&$a^nSa^{2n}$ &
                           $n\geq 0$ & $(S \,\,\,\rightarrow\,\,\, aSaa)$ \\
                         &$\Longrightarrow$&$a^nBa^{2n}$ &
                           & $(S \,\,\,\rightarrow\,\,\,  B)$ \\
                         &$\stackrel{k}{\Longrightarrow}$&$a^nb^{2k}Bd^{2k}a^{2n}$ &
                            $k\geq 0$ & $(B \,\,\,\rightarrow\,\,\,  bbBdd)$ \\
                         &$\Longrightarrow$&$a^nb^{2k}Cd^{2k}a^{2n}$ &
                           & $(B \,\,\,\rightarrow\,\,\,  C)$ \\
                         &$\Longrightarrow$&$a^nb^{2k+1}d^{2k+1}a^{2n}$ &
                           & $(B \,\,\,\rightarrow\,\,\,  bd)$
                    \end{tabular}

              \item $L(G) \subseteq X$

                    Basta mostrar que as seguintes condi\c c\~oes s\~ao
                    satisfeitas por toda forma sentencial $w$ de $G$:
                    \begin{list}{(\arabic{conta3})}{\usecounter{conta3}}
                     \item $2n_{p.a}(w)=n_{s.a}(w)$;
                     \item $n_{b}(w)=n_{d}(w)$;
                     \item $n_{b}(w)+n_{B}(w)+n_{C}(w)$ \'e \'{\i}mpar;
                     \item entre o prefixo de $a$'s, denominado $p.a$ em (1), e
                           o sufixo de $a$'s, denominado $s.a$ em (1), vem $S$ ou
                           $B$ ou $C$ ou nenhum destes, antecedido pelos $b$'s
                           (se houver algum) e sucedido pelos $d$'s (se houver
                           algum).
                    \end{list}
                    Ser\'a mostrado que estas condi\c c\~oes s\~ao satisfeitas,
                    por indu\c c\~ao sobre o tamanho das deriva\c c\~oes. Existem
                    duas deriva\c c\~oes de tamanho 1:
                    
                    \begin{tabular}{ccll}
                      $S$&$\Longrightarrow$&$aSaa$&
                           $(S \,\,\,\rightarrow\,\,\, aSaa)$ \\
                      $S$&$\Longrightarrow$&$B$&
                           $(S \,\,\,\rightarrow\,\,\,  B)$
                    \end{tabular}

                    \'E trivial verificar que cada uma das 4 condi\c c\~oes acima
                    \'e satisfeita pelas formas sentenciais $aSaa$ e $B$.
                    Suponha, ent\~ao, como hip\'otese de indu\c c\~ao, que as
                    condi\c c\~oes s\~ao satisfeitas por formas sentenciais $w$
                    obtidas por deriva\c c\~oes de tamanho $n$, ou seja, tais
                    que $S\stackrel{n}{\Longrightarrow}w$. Deve-se mostrar
                    que elas s\~ao satisfeitas por formas sentenciais $v$
                    obtidas por deriva\c c\~oes de tamanho $n+1$, ou seja, tais
                    que $S\stackrel{n+1}{\Longrightarrow}v$. Mas estas s\~ao
                    tais que $S\stackrel{n}{\Longrightarrow}w\Longrightarrow v$,
                    para alguma forma sentencial $w$. Basta ent\~ao aplicar a
                    hip\'otese de indu\c c\~ao e verificar que as 4 condi\c c\~oes
                    continuam valendo ap\'os a aplica\c c\~ao de qualquer uma
                    das 5 regras da gram\'atica; o que pode ser feito
                    trivialmente.
              \end{list}
       \end{list}
 \item {\it Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\, aSbS 
                  \,\,\,|\,\,\, \lambda$
       \end{enumerate}
       Prove que \[L(G)=\{x\in\{a,b\}^* \,\,\,|\,\,\, \mbox{todo prefixo de $x$
       tem no m\'{\i}nimo tantos $a$'s quantos $b$'s}\}\mbox{.}\]}

       Quem fizer este exerc\'{\i}cio at\'e 15/4/97 ganha 2 pontos extra. (Obs:
       se a solu\c c\~ao estiver {\bf totalmente correta}, o aluno ganha 2
       pontos; caso contr\'ario, n\~ao ganha nada.)
       
 \item {\it Uma {\em gram\'{a}tica linear \`{a} direita\/} \'{e} uma
       gram\'{a}tica livre do contexto em que cada regra tem uma das formas:
       \begin{list}{(\roman{conta})}{\usecounter{conta}}
        \item $A \,\,\,\rightarrow\,\,\, w$
        \item $A \,\,\,\rightarrow\,\,\, wB$
        \item $A \,\,\,\rightarrow\,\,\, \lambda$
       \end{list}
       onde $w\in\Sigma^+$.
       
       Prove que uma linguagem $L$ \'{e} gerada por uma gram\'{a}tica linerar a direita
       se, e somente se, $L$ \'{e} gerada por uma gram\'{a}tica regular.}

       Pelas defini\c c\~oes de ambas, toda gram\'atica regular \'e gram\'atica
       linear \`a direita. Assim, basta mostrar que, para qualquer gram\'atica
       linear \`a direita existe gram\'atica regular equivalente. Para isto,
       basta apenas mostrar como substituir as regras das formas
       $A \,\,\,\rightarrow\,\,\, a_1a_2\cdots a_n$, $n\geq 2$, e
       $A \,\,\,\rightarrow\,\,\, a_1a_2\cdots a_nB$, $n\geq 2$, por regras das
       formas permitidas em gram\'atica regulares, que propiciem exatamente o
       mesmo efeito. No primeiro caso, consegue-se isto substituindo a regra
       $A \,\,\,\rightarrow\,\,\, a_1a_2\cdots a_n$ por: 
       
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, a_1X_1$
        \item[\ ] \hspace*{1cm}$X_1 \,\,\,\rightarrow\,\,\, a_2X_2$
        \item[\ ] \hspace*{1cm}$\vdots$
        \item[\ ] \hspace*{1cm}$X_{n-1} \,\,\,\rightarrow\,\,\, a_n$
       \end{enumerate}
       
       onde $X_1, X_2, \ldots, X_{n-1}$ s\~ao vari\'aveis {\it novas\/}. J\'a
       no segundo caso, consegue-se isto substituindo a regra
       $A \,\,\,\rightarrow\,\,\, a_1a_2\cdots a_nB$ por: 
       
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, a_1Y_1$
        \item[\ ] \hspace*{1cm}$Y_1 \,\,\,\rightarrow\,\,\, a_2Y_2$
        \item[\ ] \hspace*{1cm}$\vdots$
        \item[\ ] \hspace*{1cm}$Y_{n-1} \,\,\,\rightarrow\,\,\, a_nB$
       \end{enumerate}

       onde $Y_1, Y_2, \ldots, Y_{n-1}$ s\~ao vari\'aveis {\it novas\/}.
       
\end{enumerate}

\end{document}
