\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas ne-nhum ba-lan-cea-dos}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos Te\'oricos da Computa\c c\~ao}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000
 
\noindent Professor: Newton Jos\'{e} Vieira

\noindent {\bf Terceira Lista de Exerc\'{\i}cios} \hfill Data de entrega: 09/11/2000

\section{Aut\^omatos a Pilha}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 3.2}

\begin{enumerate}

 \item Construa APD's para as seguintes linguagens:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+0+^{3n}\verb+1+^{2n}\,\,|\,\,n\geq 0\}$
          \item $\{w\verb+0+w^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
          \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n\geq 1 \mbox{ e } k\geq 0\}$
          \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m<n\}$
          \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m\not=n\}$
          \end{list}

 \item Explique porque n\~ao h\'a APD para as seguintes linguagens:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{ww^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
          \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n,k\geq 0\}$
          \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m>n\}$
         \end{list}

 \item Construa um APD que reconhe\c ca toda palavra com par\^enteses balanceados. 
       Exemplos de palavras da linguagem: $\lambda$, \verb+()+, \verb+(())()+. Exemplos de
       palavras que n\~ao pertencem \`a linguagem: \verb+(+, \verb+)(+, \verb+())+.

       Generalize para o caso em que existem $n$ tipos de par\^enteses. Neste caso, considere que
       cada ocorr\^encia de um abre par\^enteses, $a_i$, tem de ser seguida \`a direita por uma
       ocorr\^encia do fecha par\^enteses respectivo, $b_i$, sendo que entre $a_i$ e $b_i$ s\'o
       pode ocorrer uma palavra com par\^enteses balanceados. Se $i=2$, $a_1=\verb+(+$,
       $b_1=\verb+)+$, $a_2=\verb+[+$, $b_2=\verb+]+$, seriam exemplos de palavras da linguagem:
       $\lambda$, \verb+()+, \verb+[()]()+, \verb+[[()]()]([])+. Exemplos de palavras que n\~ao
       pertencem \`a linguagem: \verb+(+, \verb+][+, \verb+()]+, \verb+(]+, \verb+([)]+.


 \item Construa um APD que reconhe\c ca as express\~oes aritm\'eticas na forma prefixada, EAPre,
       definidas recursivamente como segue:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \verb+t+ \'e uma EAPre;
        \item se $x$ e $y$ s\~ao EAPre's, ent\~ao $\verb|+|xy$ e $\verb|-|xy$ s\~ao EAPre's.
       \end{list}
       {\em Sugest\~ao\/}: sempre que ler \verb|+| ou \verb|-|, empilhe dois \verb|X|'s, para
       ``lembrar'' de ler duas subexpress\~oes \`a frente.

 \item Construa um APD que reconhe\c ca as express\~oes aritm\'eticas na forma posfixada, EAPos,
       definidas recursivamente como segue:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \verb+t+ \'e uma EAPos;
        \item se $x$ e $y$ s\~ao EAPos's, ent\~ao $xy\verb|+|$ e $xy\verb|-|$ s\~ao EAPos's.
       \end{list}
       {\em Sugest\~ao\/}: use os seguintes fatos, f\'aceis de mostrar por indu\c c\~ao: o
       n\'umero de \verb|t|'s \'e um a mais que o de operadores, e qualquer palavra que tenha mais
       \verb|t|'s que operadores \'e prefixo de EAPos.

\end{enumerate}


\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 3.3}

\begin{enumerate}

 \item Construa um AP com um alfabeto de pilha contendo apenas dois s\'{\i}mbolos, que reconhe\c ca
       $\{w\in\{\verb+a+,\verb+b+,\verb+c+,\verb+d+\}^*\,\,|\,\,w=w^R\}$.

 \item Construa APND's que reconhe\c cam as linguagens seguintes por estado final e pilha
       vazia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^n\,\,|\,\,n\geq 0\}\cup\{\verb+0+^n\verb+1+^{2n}\,\,|\,\,
              n\geq 0\}$
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n\leq k\leq 2n\}$
        \item $\{\verb+0+^n\verb+1+^n\verb+0+^k\,\,|\,\,n,k\geq 0\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m>n\}$
       \end{list}

 \item Construa APND's que reconhe\c cam as linguagens do exerc\'{\i}cio 2:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item por estado final;
          \item por pilha vazia.
         \end{list}

 \item Seja $L$ uma linguagem qualquer. Mostre que as seguintes afirmativas s\~ao equivalentes:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item Existe um APND que reconhece $L$ por estado final e pilha vazia.
          \item Existe um APND que reconhece $L$ por estado final.
          \item Existe um APND que reconhece $L\cup\{\lambda\}$ por pilha vazia.
         \end{list}
         {\em Sugest\~ao\/}: mostre como transfomar um APND de um tipo em outro. Observe que bastam 3 (e n\~ao 4)
         transforma\c c\~oes, se estas forem convenientemente escolhidas.

         \label{eanbn}

\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 3.4}

\begin{enumerate}
 \item Construa GLC's para as linguagens do Exerc\'{\i}cio 2 dos exerc\'{\i}cios selecionados da
       Se\c c\~ao 3.3.

 \item Construa GLC's para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^{3m+2n+1} \,\,|\,\, m,n\geq 0\}$
        \item $\{\verb+a+^n\verb+b+^{2n+k}\verb+c+^{3k} \,\,|\,\, n,k\geq 0\}$
	 \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,\,|\,\, n>m+k\}$
       \end{list}

 \item Construa GLC's para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{\verb+0+^n\verb+1+^k\,\,|\,\, 2n\leq k \leq 3n\}$
        \item $L_2=\{\verb+a+^n\verb+b+^k\verb+c+^m\,\,|\,\,k=2n+m\}$
        \item $(L_1\cup L_2)^2$
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $\verb+a+ P \verb+b+ \,\,|\,\, \verb+a+ \verb+a+ P \verb+b+
                    \,\,|\,\, \lambda$
	\end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item Seja $G$ uma GLC que contenha, dentre outras, as regras:
	\begin{center}
	\begin{tabular}{ccl}
	 $\langle$cmd$\rangle$ & $\rightarrow$ & {\bf se} $\langle$exp-rel$\rangle$ {\bf ent\~ao}
                $\langle$cmd$\rangle$ \\
	 $\langle$cmd$\rangle$ & $\rightarrow$ & {\bf se} $\langle$exp-rel$\rangle$ {\bf ent\~ao}
                $\langle$cmd$\rangle$
                                 {\bf sen\~ao} $\langle$cmd$\rangle$
	\end{tabular}
	\end{center}
       onde $\langle$cmd$\rangle$ e $\langle$exp-rel$\rangle$ s\~ao vari\'aveis \'uteis e {\bf se},
       {\bf ent\~ao} e {\bf sen\~ao} s\~ao terminais. Mostre que $G$ \'e amb\'{\i}g\"ua. Como
       eliminar a ambig\"uidade causada por tais regras?

 \item Construa uma gram\'atica sem regras $\lambda$ equivalente
	\`a seguinte gra\-m\'a\-ti\-ca:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $B P A \,\,|\,\, A$ \\
	 $A$ & $\rightarrow$ & $\verb+a+ A \,\,|\,\, \lambda$ \\
	 $B$ & $\rightarrow$ & $B \verb+b+ \verb+a+ \,\,|\,\, \lambda$
	\end{tabular}
	\end{center}

  \item Seja a gram\'atica $G$:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $A \,\,|\,\, B C $ \\
	 $A$ & $\rightarrow$ & $B \,\,|\,\, C$ \\
	 $B$ & $\rightarrow$ & $\verb+b+ B \,\,|\,\, \verb+b+$ \\
	 $C$ & $\rightarrow$ & $\verb+c+ C \,\,|\,\, \verb+c+$ \\
	\end{tabular}
	\end{center}
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item Construa uma gram\'atica equivalente a $G$, sem regras de
	       cadeias.
	 \item Mostre que a gram\'atica constru\'{\i}da cont\'em s\'{\i}mbolos
	       in\'uteis.
	\end{list}

  \item Seja $G$ uma gram\'{a}tica e $w\in L(G)$, de tamanho $n$. Para os casos em que $G$ est\'a
        na forma normal de Chomsky e em que est\'a na forma normal de Greibach, determine:
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item O tamanho de uma deriva\c{c}\~{a}o de $w$.
	 \item A profundidade m\'{a}xima de uma AD de $w$.
	 \item A profundidade m\'{\i}nima de uma AD de $w$.
	\end{list}

 \item Obtenha um AP que reconhe\c ca a linguagem do Exerc\'{\i}cio 2(c), a partir da GLC de tal
       linguagem, usando o m\'etodo apresentado na prova do Teorema 25.

 \item Seja o aut\^{o}mato a pilha $P = (\{i\},\{\verb+(+,\verb+)+\},\{\verb+0+\},\delta,\{i\},\{i\})$
       tal que $\delta$ \'{e} dada por:
       \begin{center}
       \begin{tabular}{ccc}
        $\delta(i,\verb+(+,\lambda)$ & $=$ & $[i,\verb+0+]$ \\
        $\delta(i,\verb+)+,\verb+0+)$ & $=$ & $[i,\lambda]$
       \end{tabular}
       \end{center}
       Construa uma gram\'{a}tica livre do contexto que gere $L(P)$, utilizando
       o m\'{e}todo do Teorema 26.

 \item Seja o APD $M=(\{0,1\},\{\verb+a+,\verb+b+,\verb+c+\},\{A,B\},\delta,\{1\})$, onde $\delta$ \'e dada por:
         \begin{enumerate}
          \item[\ \ \ ] $\delta(0,\verb+a+,\lambda)=\{[0,A]\}$
          \item[\ \ \ ] $\delta(0,\verb+b+,A)=\{[1,B]\}$
          \item[\ \ \ ] $\delta(1,\verb+b+,A)=\{[1,B]\}$
          \item[\ \ \ ] $\delta(1,\verb+c+,B)=\{[1,\lambda]\}$
         \end{enumerate}
         Utilize o m\'etodo apresentado no Teorema 26 para obter uma GLC que gere $L(M)$.

\end{enumerate}


\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 3.5}

\begin{enumerate}

 \item  Use o lema do bombeamento para mostrar que
	as seguintes linguagens n\~{a}o s\~{a}o livres do contexto:
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item $\{\verb+a+^{n^2} \,\,|\,\, n\geq 0\}$
	 \item $\{\verb+a+^n\verb+b+^{2n}\verb+a+^n \,\,|\,\, n\geq 0\}$
	\end{list}

  \item Sejam $L_1=\{\verb+a+^n\verb+b+^n \,\,|\,\, n\geq 0\}$ e
        $L_2=\{w\in\{\verb+a+,\verb+b+\}^* \,\,|\,\, |w| \mbox{ \'{e} m\'{u}ltiplo de 5}\}$.
        Mostre, para cada linguagem abaixo, que ela \'e
        ou n\~ao  uma linguagem livre do contexto:
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item $\overline{L_1}$
	 \item $L_1\cap L_2$
	 \item $L_1\cap \overline{L_2}$
	\end{list}

 \item Se $X\subseteq L$ e $L$ \'e uma linguagem livre do contexto, $X$ tamb\'em \'e linguagem
       livre do contexto?

 \item Mostre que as linguagens livres do contexto s\~ao fechadas sob reverso.

 \item Mostre que sim ou que n\~ao: as linguagens livres do contexto s\~ao fechadas sob
       diferen\c ca.

 \item Construa um AP para $L_1=\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ $w$ tem mais
       \verb+1+'s que \verb+0+'s$\}$. Construa um AFD para $L_2=\{w\in\{\verb+0+,\verb+1+\}^*
       \,\,|\,\,$ $|w|\geq 2$ e o pen\'ultimo s\'{\i}mbolo de $w$ \'e \verb+1+$\}$. Usando o
       m\'etodo da prova do Teorema 29 construa um AP para $L_1\cap L_2$.
\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 3.6}

\begin{enumerate}

 \item Seja um AP cuja pilha pode conter, no m\'aximo, $n$ s\'{\i}mbolos. Que limita\c c\~oes ter\'a
       tal tipo de AP? Justifique sua resposta.

 \item Um aut\^omato a duas pilhas \'e uma s\^extupla $M=(E,\Sigma,\Gamma,\delta,I,F)$, onde:
       \begin{itemize}
        \item $E$, $\Sigma$, $\Gamma$,$I$ e $F$ s\~ao como em APND's; e
        \item $\delta$ \'e uma fun\c c\~ao de $E\times(\Sigma\cup\{\lambda\})\times(\Gamma\cup
              \{\lambda\})\times(\Gamma\cup\{\lambda\})$ para $D$, onde $D$ \'e constitu\'{\i}do dos
              subconjuntos finitos de $E\times\Gamma^*\times\Gamma^*$.
       \end{itemize}
       Uma transi\c c\~ao neste tipo de aut\^omato manipula duas pilhas simultaneamente. Assim, a
       transi\c c\~ao $[e',z_1,z_2]\in\delta(e,a,A_1,A_2)$, que pode ser representada em um diagrama
       de estados por:
         \begin{center}
         \begin{picture}(140,40)
          \put(20,20){\oval(20,20)}
          \put(20,20){\makebox(0,0){$e$}}
          \put(30,20){\vector(1,0){80}}
          \put(70,23){\makebox(0,0)[b]{$a,A_1/z_1,A_2/z_2$}}
          \put(120,20){\oval(20,20)}
          \put(120,20){\makebox(0,0){$e'$}}
         \end{picture}
         \end{center}
      significa, no caso em que nenhuma das entidades envolvidas \'e $\lambda$, que ``estando no
      estado $e$, se o pr\'oximo s\'{\i}mbolo de entrada for $a$, o s\'{\i}mbolo no topo da pilha 1
      for $A_1$ e o s\'{\i}mbolo no topo da pilha 2 for $A_2$, h\'a uma transi\c c\~ao para o estado
      $e'$, $A_1$ \'e desempilhado e $z_1$ \'e empilhado na pilha 1, e $A_2$ \'e desempilhado e
      $z_2$ \'e empilhado na pilha 2.
      Fa\c ca aut\^omatos a duas pilhas que reconhe\c cam:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\,\,|\,\,n\geq 0\}$
       \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\verb+d+^n\,\,|\,\,n\geq 0\}$
      \end{list}

 \item Na Figura 2.9 est\'a ilustrado um AFD com fita bidirecional, isto \'e, um AFD cujo cabe\c cote
       de leitura pode se movimentar para a esquerda ou para a direita ap\'os a leitura de um
       s\'{\i}mbolo. Seja um AP com este mesmo tipo de fita bidirecional. Fa\c ca uma
       for\-ma\-li\-za\-\c c\~ao deste conceito. Em
       seguida, construa, se poss\'{\i}vel, AP's com fitas bidirecionais que reconhe\c cam:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\,\,|\,\,n\geq 0\}$
         \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\verb+d+^n\,\,|\,\,n\geq 0\}$
        \end{list}

 \item Quantas deriva\c c\~oes levam \`a AD da Figura 3.13?

 \item 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 $P \,\,\,\rightarrow\,\,\, \lambda$ 
	 \item $A \,\,\,\rightarrow\,\,\, a$
	 \item $A \,\,\,\rightarrow\,\,\, aB$
	 \item $A \,\,\,\rightarrow\,\,\, aBC$
	\end{list}
	onde $P$ \'e a vari\'avel de partida e $A, B, C \in V$ e $a \in \Sigma$.
        ({\em Sugest\~{a}o\/}: parta de uma gram\'{a}tica na forma normal de Greibach.)

 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L-F$ \'{e} linguagem livre do contexto.
        \item Se $L$ \'{e} uma linguagem livre do contexto e $R$ \'{e} regular, ent\~{a}o
              $L-R$ \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L-F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e} regular, ent\~{a}o
              $L-R$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L\cup F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e} regular, ent\~{a}o
              $L\cup R$ n\~{a}o \'{e} linguagem livre do contexto.
       \end{list}

\end{enumerate}


\end{document}
 
