\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\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 Lista de Exerc\'{\i}cios}

\vspace*{3mm}
\noindent \underline{Observa\c{c}\~{a}o}: Os n\'{u}meros dos exerc\'{\i}cios extra\'{\i}dos de livros
indicados no Plano de Curso est\~{a}o apresentados seguidos das iniciais dos autores
concatenadas com os dois \'{u}ltimos d\'{\i}gitos do ano da publica\c{c}\~{a}o do livro.

\setcounter{section}{2}

\section{Gram\'{a}ticas Livres do Contexto}
 
\begin{enumerate}
 \item (2, cap. 3 de S88) 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 D\^{e} uma deriva\c{c}\~{a}o mais a esquerda de $aabbba$.
        \item D\^{e} uma deriva\c{c}\~{a}o mais a direita de $abaabbbabbaa$.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es das partes
              (a) e (b).
        \item Use nota\c{c}\~{a}o de conjunto para definir $L(G)$.
       \end{list}
 \item (3, cap. 3 de S88) 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 D\^{e} uma deriva\c{c}\~{a}o mais a esquerda que gere a \'{a}rvore {\em AD\/}.
        \item D\^{e} uma deriva\c{c}\~{a}o mais a direita que gere a \'{a}rvore {\em AD\/}.
        \item Quantas deriva\c{c}\~{o}es diferentes geram {\em AD\/}?
       \end{list}
 \item Construa uma gram\'{a}tica regular para cada uma das linguagens do exerc\'{\i}cio
       2.5 da primeira Lista.
 \item (3.3.3 de K95) Construa uma gram\'{a}tica para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^mb^n \,\,\,|\,\,\, m>n\}$.
        \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}\}$.
        \item $\{a^mb^n \,\,\,|\,\,\, n\leq m \leq 2n\}$.
        \item $\{a^mb^nc^pd^q \,\,\,|\,\,\, m+n \geq p+q\}$.
       \end{list}
 \item (30, cap. 3 de S88) 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 O que \'{e} $L(G)$?
        \item Prove que $L(G)$ \'{e} o conjunto dado em (a).
       \end{list}
 \item (4.2 de HU79) 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{.}\]
       
 \item (38, cap. 3 de S88) 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.
\end{enumerate}

\section{An\'{a}lise Sint\'{a}tica: Uma Introdu\c{c}\~{a}o}

\begin{enumerate}
 \item (3, cap. 4 de S88) 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 D\^{e} uma express\~{a}o regular para $L(G)$.
        \item Construa duas deriva\c{c}\~{o}es mais a esquerda de $aabb$.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es da parte (b).
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}
 \item (7, cap. 4 de S88) 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 Defina $L(G)$ usando nota\c{c}\~{a}o de conjunto.
        \item Mostre que $G$ \'{e} amb\'{\i}gua.
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}
 \item (9, cap. 4 de S88) Construa duas gram\'{a}ticas, uma amb\'{\i}gua e outra n\~{a}o, que
       gerem a linguagem {\boldmath $a^*$}.
 \item (3.4.4 de K95) \'{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.
 \item 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?
\end{enumerate}


\section{Formas Normais}

\begin{enumerate}
 \item (3, cap. 5 de S88) Construa uma gram\'{a}tica essencialmente n\~{a}o decrescente,
       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}
 \item (14, cap. 5 de S88) Mostre que 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}
 \item (17, cap. 3 de S88) 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 Construa uma gram\'{a}tica $G_L$ essencialmente n\~{a}o decrescente,
              com um s\'{\i}mbolo de partida n\~{a}o recursivo, equivalente a $G$.
        \item Construa uma gram\'{a}tica $G_C$, sem regras de cadeias, equivalente
              a $G_L$.
        \item Construa uma gram\'{a}tica na forma normal de Chomsky equivalente
              a $G_C$.
       \end{list}
 \item (19, cap. 3 de S88) Seja $G$ uma gram\'{a}tica na forma normal de Chomsky.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Qual \'{e} o tamanho de uma deriva\c{c}\~{a}o de um {\em string\/} $w\in L(G)$
              de tamanho $n$?
        \item 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$?
        \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$?
       \end{list}
 \item (21, cap. 3 de S88) 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}
 \item (27, cap. 3 de S88) 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.)
\end{enumerate}
 
\end{document}
\endinput
\end
                            
