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

\begin{flushleft} \large\bf
 {Aut\^{o}matos a Pilha e Linguagens Livres do Contexto}
\end{flushleft}

\begin{enumerate}
 \item {\it Construa aut\^{o}matos a pilha (AP) para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i+k=j\}$
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i=j \mbox{ ou } j=k\}$
        \item $\{a^ib^j \,\,\,|\,\,\, i\not=j\}$
        \item $\{a^ib^j \,\,\,|\,\,\, i\leq j\leq 2i\}$
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i+k=j\}$
        
              $(\{q_0,q_1,q_2,q_3\},\{a,b,c\},\{A,B\},\delta,q_0,\{q_3\})$, onde
              $\delta$ \'e dada por:
              
              $\delta(q_0,a,\lambda)=\{[q_0,A]\}$ \\
              $\delta(q_0,\lambda,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,\lambda,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,b,\lambda)=\{[q_2,B]\}$ \\
              $\delta(q_2,\lambda,\lambda)=\{[q_3,\lambda]\}$ \\
              $\delta(q_3,c,B)=\{[q_3,\lambda]\}$
        
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i=j \mbox{ ou } j=k\}$
        
              $(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\},\{a,b,c\},\{A\},\delta,q_0,
              \{q_3,q_6\})$, onde $\delta$ \'e dada por:
              
              $\delta(q_0,\lambda,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_0,\lambda,\lambda)=\{[q_4,\lambda]\}$ \\
              $\delta(q_1,a,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,\lambda,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,b,\lambda)=\{[q_2,A]\}$ \\
              $\delta(q_2,\lambda,\lambda)=\{[q_3,\lambda]\}$ \\
              $\delta(q_3,c,A)=\{[q_3,\lambda]\}$ \\
              $\delta(q_4,a,\lambda)=\{[q_4,A]\}$ \\
              $\delta(q_4,\lambda,\lambda)=\{[q_5,\lambda]\}$ \\
              $\delta(q_5,b,A)=\{[q_5,\lambda]\}$ \\
              $\delta(q_5,\lambda,\lambda)=\{[q_6,\lambda]\}$ \\
              $\delta(q_6,c,\lambda)=\{[q_6,\lambda]\}$
        
        \item $\{a^ib^j \,\,\,|\,\,\, i\not=j\}$
        
              $(\{q_0,q_1,q_2,q_3\},\{a,b\},\{A\},\delta,q_0,\{q_1,q_2,q_3\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,a,\lambda)=\{[q_0,A]\}$ \\
              $\delta(q_0,b,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_0,a,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_1,b,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_2,a,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,b,A)=\{[q_3,\lambda]\}$ \\
              $\delta(q_3,b,A)=\{[q_3,\lambda]\}$
        
        \item $\{a^ib^j \,\,\,|\,\,\, i\leq j\leq 2i\}$
        
              $(\{q_0,q_1,q_2\},\{a,b\},\{A\},\delta,q_0,\{q_1\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,\lambda,\lambda)=\{[q_1,\lambda]\}$ \\
              $\delta(q_0,a,\lambda)=\{[q_2,A]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_2,\lambda,\lambda)=\{[q_0,\lambda]\}$ \\
              $\delta(q_2,\lambda,\lambda)=\{[q_0,A]\}$
        
       \end{list}
       
 \item {\it Encontre um AP que aceite $aa^*ba$. A presen\c{c}a de um
       dispositivo de mem\'{o}ria em um aut\^{o}mato pode permitir uma certa economia
       de estados. Um aut\^{o}mato finito para a linguagem acima tem,
       necessariamente, no m\'{\i}nimo 4 estados, e consequentemente um AP para a
       mesma linguagem, que ignore a pilha, deve ter tamb\'{e}m no m\'{\i}nimo 4 estados.
       Encontre um AP para $aa^*ba$ com apenas 2 estados.}
       
       $(q_0,\{a,b\},\{A,B\},\delta,q_0,\{q_1\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,a,\lambda)=\{[q_0,\lambda]\}$ \\
              $\delta(q_0,a,\lambda)=\{[q_1,B]\}$ \\
              $\delta(q_1,b,B)=\{[q_1,A]\}$ \\
              $\delta(q_1,a,A)=\{[q_1,\lambda]\}$
       
 \item {\it Use a t\'{e}cnica do teorema 8.3.1 de S88 para construir um AP
       que aceite a linguagem gerada pela gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aABA \,\,\,|\,\,\,
                  aBB$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bA \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, cB \,\,\,|\,\,\, c$
       \end{enumerate}}
       
       $(q_0,\{a,b\},\{A,B\},\delta,q_0,\{q_1\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,a,\lambda)=\{[q_1,ABA]\}$ \\
              $\delta(q_0,a,\lambda)=\{[q_1,BB]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,A]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,c,B)=\{[q_1,B]\}$ \\
              $\delta(q_1,c,B)=\{[q_1,\lambda]\}$
       
       
 \item {\it Seja $L$ a linguagem $\{w\in\{a,b\}^*\,\,\,|\,\,\, 
       w$ tem prefixo contendo mais $b$'s que $a$'s$\}$. Por exemplo,
       $baa, abba, abbaaa\in L$, mas $aab, aabbab\not\in L$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AP que aceite $L$ por estado final.
        \item Construa um AP que aceite $L$ por pilha vazia.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AP que aceita $L$ por estado final:

              $(q_0,\{a,b\},\{A,X\},\delta,q_0,\{q_2\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,\lambda,\lambda)=\{[q_1,X]\}$ \\
              $\delta(q_1,a,\lambda)=\{[q_1,A]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,b,X)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,a,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,b,\lambda)=\{[q_2,\lambda]\}$

        \item AP que aceita $L$ por pilha vazia:

              $(q_0,\{a,b\},\{A\},\delta,q_0)$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,\lambda,\lambda)=\{[q_1,A]\}$ \\
              $\delta(q_1,a,\lambda)=\{[q_1,A]\}$ \\
              $\delta(q_1,b,A)=\{[q_1,\lambda]\}$ \\
              $\delta(q_1,b,A)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,a,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,b,\lambda)=\{[q_2,\lambda]\}$

       \end{list}
       
 \item {\it Use o para mostrar que
       as seguintes linguagens n\~{a}o s\~{a}o livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^k \,\,\,|\,\,\, k \mbox{ \'{e} um quadrado perfeito}\}$.
        \item $\{a^ib^{2i}a^i \,\,\,|\,\,\, i\geq 0\}$.
        \item $\{ww^Rw \,\,\,|\,\,\, w\in \{a,b\}^*\}$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L=\{a^k \,\,\,|\,\,\, k \mbox{ \'{e} um quadrado perfeito}\}$
        
              Suponha que $L$ \'e livre do contexto. Seja $k$ a constante do
              {\em pumping lemma\/}, e $z=a^{k^2}$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito como $uvwxy$, onde $|vwx|\leq k$, $|vx|>0$ e
              $uv^iwx^iy\in L$ para todo $i\geq 0$. Mas, $uv^2wx^2y\not\in z$,
              pois (a) $|uv^2wx^2y|>k^2$, j\'a que $|vx|>0$, e (b)
              $|uv^2wx^2y|=k^2+|vx|\leq k^2+k<(k+1)^2$.
        
        \item $L=\{a^ib^{2i}a^i \,\,\,|\,\,\, i\geq 0\}$
        
              Suponha que $L$ \'e livre do contexto. Seja $k$ a constante do
              {\em pumping lemma\/}, e $z=a^kb^{2k}a^k$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito como $uvwxy$, onde $|vwx|\leq k$, $|vx|>0$ e
              $uv^iwx^iy\in L$ para todo $i\geq 0$. Mas, $uv^0wx^0y\not\in z$,
              pois $uv^0wx^0y$, dado que $|vwx|\leq k$, n\~ao diminui
              s\'{\i}mbolos das 3 partes ao mesmo tempo: prefixo $a^k$,
              $b^{2k}$, e sufixo $a^k$; mas diminui de pelo menos uma delas, j\'a
              que $|vx|>0$.
        
        \item $\{ww^Rw \,\,\,|\,\,\, w\in \{a,b\}^*\}$
        
              Suponha que $L$ \'e livre do contexto. Seja $k$ a constante do
              {\em pumping lemma\/}, e $z=a^kbba^ka^kb$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito como $uvwxy$, onde $|vwx|\leq k$, $|vx|>0$ e
              $uv^iwx^iy\in L$ para todo $i\geq 0$. Mas, $uv^0wx^0y\not\in z$,
              como pode ser facilmente verificado.
        
       \end{list}
       
 \item {\it Mostre que $\{a^nb^n\,\,\,|\,\,\, n\geq 0 \mbox{ e $n$ n\~{a}o
       \'{e} m\'{u}ltiplo de 5}\}$ \'{e} uma linguagem livre do contexto.}

       Segue uma gram\'atica que reconhece a linguagem em quest\~ao:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$R_0 \,\,\,\rightarrow\,\,\, aR_1b$ 
        \item[\ ] \hspace*{1cm}$R_1 \,\,\,\rightarrow\,\,\, aR_2b \,\,\,|\,\,\,
                   \lambda$
        \item[\ ] \hspace*{1cm}$R_2 \,\,\,\rightarrow\,\,\, aR_3b \,\,\,|\,\,\,
                   \lambda$
        \item[\ ] \hspace*{1cm}$R_3 \,\,\,\rightarrow\,\,\, aR_4b \,\,\,|\,\,\,
                   \lambda$
        \item[\ ] \hspace*{1cm}$R_4 \,\,\,\rightarrow\,\,\, aR_0b \,\,\,|\,\,\,
                   \lambda$
       \end{enumerate}


 \item {\it \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD $N$ que aceite os {\em strings\/} de $\{a,b\}^*$
              com n\'{u}mero \'{\i}mpar de $a$'s.
        \item Construa um AP $M$ que aceite $\{a^{3i}b^i \,\,\,|\,\,\, i\geq 0
              \}$.
        \item Use a t\'{e}cnica do teorema 8.5.3 de S88 para construir um AP que
              aceite $L(N)\cap L(M)$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFD, $N$, que aceita os {\em strings\/} de $\{a,b\}^*$
              com n\'{u}mero \'{\i}mpar de $a$'s:

              $N=(\{p,i\},\{a,b\},\delta,p,\{i\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(p,b)=p\}$ \\
              $\delta(p,a)=i\}$ \\
              $\delta(i,b)=i\}$ \\
              $\delta(i,a)=p$

        \item AP, $M$, que aceita $\{a^{3i}b^i \,\,\,|\,\,\, i\geq 0\}$:

              $M=(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\{A\},\delta,q_0,\{q_4\})$,
              onde $\delta$ \'e dada por:
              
              $\delta(q_0,a,\lambda)=\{[q_1,A]\}$ \\
              $\delta(q_1,a,\lambda)=\{[q_2,\lambda]\}$ \\
              $\delta(q_2,a,\lambda)=\{[q_3,\lambda]\}$ \\
              $\delta(q_3,a,\lambda)=\{[q_1,A]\}$ \\
              $\delta(q_3,b,A)=\{[q_4,\lambda]\}$ \\
              $\delta(q_4,b,A)=\{[q_4,\lambda]\}$

        \item AP que aceita $L(N)\cap L(M)$:

              $M=(\{q_0p,q_1i,q_1p,q_2p,q_2i,q_3i,q_3p,q_4i,q_4p\},\{a,b\},
              \{A\},\delta,q_0p,\{q_4i\})$, onde $\delta$ \'e dada por:
              
              $\delta(q_0p,a,\lambda)=\{[q_1i,A]\}$ \\
              $\delta(q_1i,a,\lambda)=\{[q_2p,\lambda]\}$ \\
              $\delta(q_1p,a,\lambda)=\{[q_2i,\lambda]\}$ \\
              $\delta(q_2p,a,\lambda)=\{[q_3i,\lambda]\}$ \\
              $\delta(q_2i,a,\lambda)=\{[q_3p,\lambda]\}$ \\
              $\delta(q_3i,a,\lambda)=\{[q_1p,\lambda]\}$ \\
              $\delta(q_3i,b,A)=\{[q_4i,\lambda]\}$ \\
              $\delta(q_3p,a,\lambda)=\{[q_1i,\lambda]\}$ \\
              $\delta(q_3p,b,A)=\{[q_4p,\lambda]\}$ \\
              $\delta(q_4i,b,A)=\{[q_4i,\lambda]\}$ \\
              $\delta(q_4p,b,A)=\{[q_4p,\lambda]\}$

       \end{list}       
       
 \item {\it Seja $L=\{a^ib^jc^k \,\,\,|\,\,\, i\not=j \mbox{ ou } j\not=k\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $L$ \'{e} uma linguagem livre do contexto.
        \item Mostre que se $\Sigma$ \'{e} qualquer alfabeto tal que $L\subseteq
              \Sigma^*$, ent\~{a}o $\Sigma^*-L$ n\~{a}o \'{e} uma linguagem livre do
              contexto. ({\em Sugest\~{a}o\/}: considere a linguagem {\boldmath
              $a^*b^*c^*$}.)
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostrando que $L$ \'{e} uma linguagem livre do contexto.
              
              $L=L_1\cup L_2$, onde $L1=\{a^ib^jc^k \,\,\,|\,\,\, i\not=j\}$ e
              $L2=\{a^ib^jc^k \,\,\,|\,\,\, j\not=k\}$. Como as linguagens livres
              do contexto s\~ao fechadas sob uni\~ao, basta mostrar que $L_1$ e
              $L_2$ s\~ao linguagens livres do contexto. Uma gram\'atica para
              $L_1$:
              \begin{enumerate}
               \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, XC$ 
               \item[\ ] \hspace*{1cm}$X \,\,\,\rightarrow\,\,\, aXb
                          \,\,\,|\,\,\, aA \,\,\,|\,\,\, bB$
               \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA
                          \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB
                          \,\,\,|\,\,\, \lambda$
               \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC
                          \,\,\,|\,\,\, \lambda$
              \end{enumerate}
              Existe uma gram\'atica an\'aloga para $L_2$.

        \item MOstrando que, se $\Sigma$ \'{e} qualquer alfabeto tal que $L\subseteq \Sigma^*$,
              ent\~{a}o $\Sigma^*-L$ n\~{a}o \'{e} uma linguagem livre do
              contexto.

              Pode-se dizer que $L$ \'e uma liguagem no alfabeto $\Sigma$
              (com a possibilidade de alguns s\'{\i}mbolos de $\Sigma$ n\~ao
              ocorrerem em {\it strings\/} de $L$). Assim, $\Sigma^*-L=
              \overline{L}$. Suponha, ent\~ao, que $\overline{L}$ \'e uma
              linguagem livre do contexto. Neste caso, como {\boldmath
              $a^*b^*c^*$} \'e regular, $\overline{L}\cap a^*b^*c^*$ teria que
              ser livre do contexto. Mas, $\overline{L}\cap a^*b^*c^*=
              \{a^ib^ic^i \,\,|\,\, i\geq 0\}$, que n\~ao \'e livre do contexto.
              Portanto, a suposi\c c\~ao original que $\overline{L}$ seria
              livre do contexto n\~ao \'e correta.

       \end{list}
       
 \item {\it Prove que o conjunto das linguagens livres do contexto \'{e}
       fechado sob reverso.}
       
       Seja uma gram\'atica $G=(V,\Sigma,P,S)$. A gram\'atica
       \[G'=(V,\Sigma,\{A \,\rightarrow\, w^R \,\,\,|\,\,\,\
        A \,\rightarrow\, w\in P\},S)\]
        \'e tal que $L(G')=L(G)^R$.
       
\end{enumerate}
 
\end{document}
