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

\begin{flushleft} \large\bf
 {Formas Normais}
\end{flushleft}


\begin{enumerate}
 \item {\it Construa uma gram\'{a}tica essencialmente n\~{a}o contr\'actil,
       com um s\'{\i}mbolo de partida n\~{a}o recursivo, equivalente \`{a}
       gram\'{a}tica:}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, BSA \,\,\,|\,\,\, A$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, Bba \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
       
       Para eliminar a recursividade do s\'{\i}mbolo de partida, basta
       acrescentar a regra $S' \,\,\,\rightarrow\,\,\, S$, e considerar
       $S'$ como o novo s\'{\i}mbolo de partida. Para obter uma
       gram\'atica essencialmente n\~ao contr\'actil equivalente, determina-se,
       inicialmente, o conjunto das vari\'aveis anul\'aveis:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$\mbox{NULL} = \{A,B,S,S'\}$.
       \end{enumerate}
       Obt\'em-se, ent\~ao, a gram\'atica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, S \,\,\,|\,\,\,
                   \lambda$
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, BSA \,\,\,|\,\,\,
                   SA \,\,\,|\,\,\, BA \,\,\,|\,\,\, BS \,\,\,|\,\,\
                   A \,\,\,|\,\,\, B$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, a$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, Bba \,\,\,|\,\,\,
                  ba$
       \end{enumerate}
       
 \item {\it Mostre que todos os s\'{\i}mbolos da gram\'{a}tica abaixo
       s\~{a}o \'{u}teis. Construa uma gram\'{a}tica $G_C$, sem regras de
       cadeia, equivalente \`{a} mesma. Mostre que $G_C$ cont\'{e}m
       s\'{\i}mbolos in\'{u}teis.}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, A \,\,\,|\,\,\, CB$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, C \,\,\,|\,\,\, D$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\, c$
        \item[\ ] \hspace*{1cm}$D \,\,\,\rightarrow\,\,\, dD \,\,\,|\,\,\, d$
       \end{enumerate}
       
       Construindo-se TERM e REACH, verifica-se que todos os s\'{\i}mbolos s\~ao
       \'uteis. Para construir uma gram\'{a}tica $G_C$, sem regras de cadeia,
       equivalente \`a acima, determina-se primeiramente CHAIN($X$), para cada
       vari\'avel $X$:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(S) = \{S,A,C,D\}$;
        \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(A) = \{A,C,D\}$;
        \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(B) = \{B\}$;
        \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(C) = \{C\}$;
        \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(D) = \{D\}$.
       \end{enumerate}
       Obt\'em-se, ent\~ao, $G_C$:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, CB \,\,\,|\,\,\, cC
                   \,\,\,|\,\,\, c \,\,\,|\,\,\, dD \,\,\,|\,\,\, d$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\, c
                   \,\,\,|\,\,\, dD \,\,\,|\,\,\, d$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\, c$
        \item[\ ] \hspace*{1cm}$D \,\,\,\rightarrow\,\,\, dD \,\,\,|\,\,\, d$
       \end{enumerate}
       Agora, v\^e-se que $\mbox{REACH}=\{S,C,B,D\}$, e, portanto, a vari\'avel
       $A$ \'e in\'util.
       
 \item {\it Seja $G$ a gram\'{a}tica}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AB \,\,\,|\,\,\, BCS$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, C$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it Construa uma gram\'{a}tica $G_L$ essencialmente n\~{a}o
              contr\'actil, com um s\'{\i}mbolo de partida n\~{a}o recursivo,
              equivalente a $G$.}
              
              Eliminando a recursividade do s\'{\i}mbolo de partida, como no
              exerc\'{\i}cio 1, calcula-se em seguida
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$\mbox{NULL} = \{C,A\}$.
              \end{enumerate}
              Com isto, obt\'em-se $G_L$:
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, S$ 
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AB
                          \,\,\,|\,\,\, B \,\,\,|\,\,\, BCS \,\,\,|\,\,\, BS$ 
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, a \,\,\,|\,\,\, C$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbB
                          \,\,\,|\,\,\, b$
               \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC
                          \,\,\,|\,\,\, c$
              \end{enumerate}

        \item {\it Construa uma gram\'{a}tica $G_C$, sem regras de cadeias,
              equivalente a $G_L$.}

              Determina-se primeiramente CHAIN($X$), para cada vari\'avel $X$:
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(S') = \{S',S,B\}$;
               \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(S) = \{S,B\}$;
               \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(A) = \{A,C\}$;
               \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(B) = \{B\}$;
               \item[\ ] \hspace*{1cm}$\mbox{CHAIN}(C) = \{C\}$.
              \end{enumerate}
              Obt\'em-se, ent\~ao, $G_C$:
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, AB
                          \,\,\,|\,\,\, BCS \,\,\,|\,\,\, BS \,\,\,|\,\,\,
                          bbB \,\,\,|\,\,\, b$ 
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AB
                          \,\,\,|\,\,\, BCS \,\,\,|\,\,\, BS \,\,\,|\,\,\,
                          bbB \,\,\,|\,\,\, b$ 
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, a \,\,\,|\,\,\, cC \,\,\,|\,\,\, c$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbB
                          \,\,\,|\,\,\, b$
               \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC
                          \,\,\,|\,\,\, c$
              \end{enumerate}
              
        \item {\it Construa uma gram\'{a}tica na forma normal de Chomsky
              equivalente a $G_C$.}
              
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, AB
                          \,\,\,|\,\,\, BX_1 \,\,\,|\,\,\, BS \,\,\,|\,\,\,
                          T_2X_2 \,\,\,|\,\,\, b$ 
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AB
                          \,\,\,|\,\,\, BX_1 \,\,\,|\,\,\, BS \,\,\,|\,\,\,
                          T_2X_2 \,\,\,|\,\,\, b$ 
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, T_1A
                          \,\,\,|\,\,\, a \,\,\,|\,\,\, T_3C \,\,\,|\,\,\, c$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, T_2X_2
                          \,\,\,|\,\,\, b$
               \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, T_3C
                          \,\,\,|\,\,\, c$
               \item[\ ] \hspace*{1cm}$X_1 \,\,\,\rightarrow\,\,\, CS$
               \item[\ ] \hspace*{1cm}$X_2 \,\,\,\rightarrow\,\,\, T_2B$
               \item[\ ] \hspace*{1cm}$T_1 \,\,\,\rightarrow\,\,\, a$
               \item[\ ] \hspace*{1cm}$T_2 \,\,\,\rightarrow\,\,\, b$
               \item[\ ] \hspace*{1cm}$T_3 \,\,\,\rightarrow\,\,\, c$
              \end{enumerate}
              
       \end{list}
 \item {\it Seja $G$ uma gram\'{a}tica na forma normal de Chomsky.}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it Qual \'{e} o tamanho de uma deriva\c{c}\~{a}o de um {\em
              string\/} $w\in L(G)$ de tamanho $n$?}
              \[\left\{\begin{array}{ll} 1 & \mbox{\it se } n=0 \\
                                     2n-1 & \mbox{\it se } n\geq 1
                        \end{array}\right.\]
              No primeiro caso, a deriva\c c\~ao seria $S \,\,\Longrightarrow
              \,\, \lambda$. No outro, s\~ao usadas regras da forma
              $A \,\,\rightarrow\,\, BC$ $n-1$ vezes, e regras da forma
              $A \,\,\rightarrow\,\, a$ $n$ vezes (uma para cada terminal do
              {\it string\/}).
              
        \item {\it Qual \'{e} a profundidade m\'{a}xima de uma \'{a}rvore de
              deriva\c{c}\~{a}o para um {\em string\/} $w\in L(G)$ de tamanho
              $n$?}
              
              Verifica-se facilmente que \'e:
              \[\left\{\begin{array}{ll} 1 &\mbox{\it se } n=0\\
                                     n &\mbox{\it se } n\geq 1
                        \end{array}\right.\]
              
        \item Qual \'{e} a profundidade m\'{\i}nima de uma \'{a}rvore de deriva\c{c}\~{a}o para um
              {\em string\/} $w\in L(G)$ de tamanho $n$?
              
              Verifica-se facilmente que \'e:
              \[\left\{\begin{array}{ll} 1 &\mbox{\it se } n=0 \mbox{ ou } n=1\\
                                     \lceil log_2n\rceil +1
                                       &\mbox{\it se } n\geq 2
                        \end{array}\right.\]
              
       \end{list}
 \item {\it Construa uma gram\'{a}tica na forma normal de Greibach equivalente
       \`{a} gram\'{a}tica:}
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\, a$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, SS \,\,\,|\,\,\, b$
       \end{enumerate}
       
       Retirando a recursividade do s\'{\i}mbolo de partida e regras de cadeia:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\, a$ 
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\, a$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, SS \,\,\,|\,\,\, b$
       \end{enumerate}
       Aplicando o lema 5.6.2 do livro texto (neste exemplo, a numera\c c\~ao
       das vari\'aveis n\~ao \'e importante; qualquer uma das duas d\'a na
       mesma):
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S' \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\,
                   a$ 
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\, a$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aAbS \,\,\,|\,\,\,
                   aS\,\,\,|\,\,\, b$
       \end{enumerate}
       E pronto!
 \item {\it Prove que toda linguagem livre do contexto \'{e} gerada por uma
       gram\'{a}tica na qual cada uma das regras \'{e} de uma das formas:
       \begin{list}{(\roman{conta})}{\usecounter{conta}}
        \item $S \,\,\,\rightarrow\,\,\, \lambda$ 
        \item $A \,\,\,\rightarrow\,\,\, a$
        \item $A \,\,\,\rightarrow\,\,\, aB$
        \item $A \,\,\,\rightarrow\,\,\, aBC$
       \end{list}
       onde $A, B, C \in V$ e $a \in \Sigma$. ({\em Sugest\~{a}o\/}: parta de
       uma gram\'{a}tica na forma normal de Greibach.)}
       
       
       Partindo de uma gram\'{a}tica na forma normal de Greibach, as \'unicas
       regras da mesma que, eventualmente, n\~ao tenham uma das formas acima,
       ter\~ao a forma: 
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aB_1B_2\ldots B_n$,
                  $n\geq 3$.
       \end{enumerate}
       Neste caso, substitua, inicialmente, cada regra desta pelas regras:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aX_1$
        \item[\ ] \hspace*{1cm}$X_1 \,\,\,\rightarrow\,\,\, B_1X_2$
        \item[\ ] \hspace*{1cm}$X_2 \,\,\,\rightarrow\,\,\, B_2X_3$
        \item[\ ] \hspace*{1cm}$\vdots$
        \item[\ ] \hspace*{1cm}$X_{n-1} \,\,\,\rightarrow\,\,\, B_{n-1}B_n$
       \end{enumerate}
       onde $X_1, X_2, \ldots, X_{n-1}$ s\~ao vari\'aveis {\it novas\/}.
       Observe que, ap\'os todas as substitui\c c\~oes, as regras $B_i$ ser\~ao
       da forma $B_i\,\,\rightarrow aC$ e/ou $B_i\,\,\rightarrow a$. Assim,
       aplicando-se o lema 5.6.2 com rela\c c\~ao \`as regras dos tipos
       $X_i \,\,\rightarrow\,\, B_iX_{i+1}$ e $X_{n-1} \,\,\rightarrow\,\, B_{n-1}B_n$,
       obt\'em-se apenas regras no formato desejado.

       
\end{enumerate}
 
\end{document}
