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

\begin{flushleft} \large\bf
 {A Hierarquia de Chomsky}
\end{flushleft}


\begin{enumerate}
 \item {\it Construa gram\'{a}ticas irrestritas para gerar as seguintes
       linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j\geq 0\}$
        \item $\{a^ib^ic^id^i \,\,\,|\,\,\, i\geq 0\}$
        \item $\{www \,\,\,|\,\,\, w\in \{a,b\}^*\}$
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j\geq 0\}$
        
              \begin{tabular}{lcl}
               $S$ & $\rightarrow$ & $A\#$ \\
               $A$ & $\rightarrow$ & $aAa \,\,|\,\, X$ \\
               $X$ & $\rightarrow$ & $bXB \,\,|\,\, \lambda$ \\
               $Ba$ & $\rightarrow$ & $aB$ \\
               $B\#$ & $\rightarrow$ & $\#b$ \\
               $\#$ & $\rightarrow$ & $\lambda$
              \end{tabular}
              
        \item $\{a^ib^ic^id^i \,\,\,|\,\,\, i\geq 0\}$
        
              \begin{tabular}{lcl}
               $S$ & $\rightarrow$ & $aBSCd \,\,|\,\, \lambda$ \\
               $BC$ & $\rightarrow$ & $bc$ \\
               $Ba$ & $\rightarrow$ & $aB$ \\
               $Bb$ & $\rightarrow$ & $bb$ \\
               $dC$ & $\rightarrow$ & $Cd$ \\
               $cC$ & $\rightarrow$ & $cc$
              \end{tabular}
        
        \item $\{www \,\,\,|\,\,\, w\in \{a,b\}^*\}$
        
              \begin{tabular}{lcl}
               $S$ & $\rightarrow$ & $X[\,\,]$ \\
               $X$ & $\rightarrow$ & $aXA \,\,|\,\, bXB \,\,|\,\, \lambda$ \\
               $Aa$ & $\rightarrow$ & $aA$ \\
               $Ab$ & $\rightarrow$ & $bA$ \\
               $Ba$ & $\rightarrow$ & $aB$ \\
               $Bb$ & $\rightarrow$ & $bB$ \\
               $A[$ & $\rightarrow$ & $a[A$ \\
               $B[$ & $\rightarrow$ & $b[B$ \\
               $A]$ & $\rightarrow$ & $a]$ \\
               $B]$ & $\rightarrow$ & $b]$ \\
               $[$ & $\rightarrow$ & $\lambda$ \\
               $]$ & $\rightarrow$ & $\lambda$
              \end{tabular}
        
       \end{list}
       
 \item {\it Seja $L$ uma linguagem recursivamente enumer\'{a}vel sobre $\Sigma$,
       e $c$ um s\'{\i}mbolo terminal n\~{a}o pertencente a $\Sigma$. Mostre que
       existe uma linguagem sens\'{\i}vel ao contexto $L'$ sobre $\Sigma\cup
       \{c\}$ tal que, para todo $w\in \Sigma^*$, $w\in L$ se, e somente se,
       $wc^i\in L'$ para algum $i\geq 0$.}
       
       Uma gram\'atica sens\'{\i}vel ao contexto, $G'$, que reconhece uma linguagem
       $L'$ como especificado acima, pode ser constru\'{\i}da a partir de uma
       gram\'atica irrestrita $G=(V,\Sigma,P,S)$ que reconhece $L$, da seguinte
       forma:
       \begin{enumerate}
        \item[.] Seja $S'$ a vari\'avel de partida de $G'$, $S'\not\in V$;
        \item[.] coloque a regra $S' \,\,\rightarrow\,\, Sc$ em $G'$;
        \item[.] coloque em $G'$ toda regra de $G$ da forma $u \,\,\rightarrow
                 \,\, v$ tal que $|u|\leq |v|$;
        \item[.] coloque em $G'$ uma regra $u \,\,\rightarrow \,\, 
                 vC^{|u|-|v|}$ para cada regra de $G$ da forma
                 $u \,\,\rightarrow\,\, v$  tal que $|u|>|v|$, sendo $C$ uma
                 vari\'avel que n\~ao ocorra em $V\cup\{S'\}$;
        \item[.] coloque em $G'$ uma regra $Ca \,\,\rightarrow \,\, aC$ para
                 $a\in \Sigma$;
        \item[.] e, finalmente, coloque em $G'$ a regra $Cc \,\,\rightarrow
                 \,\, cc$.
       \end{enumerate}
       
 \item {\it Seja {\cal C} uma classe de dispositivos de alguma esp\'{e}cie.
       Suponha que {\cal C} pode ser enumerada: $M_1$, $M_2$, \ldots.
       Suponha ainda que exista um algoritmo que, quando recebe um dispositivo
       $M$ de {\cal C} e uma entrada $w$, determina se $M$ aceita $w$. Mostre
       que nem toda linguagem recursiva sobre um alfabeto $\Sigma$ \'{e}
       aceita por algum dispositivo em {\cal C}.}
       
       Seja $A$ um algoritmo (m\'aquina de Turing) que determina, para cada
       dispositivo $M_i$ de {\cal C} e cada entrada $w$, se $M_i$ aceita $w$. A
       linguagem
       \[\{R(M_i) \,\,|\,\, M_i \mbox{\it  n\~ao aceita $R(M_i)$}\}\]
       \'e recursiva, pois \'e aceita por uma m\'aquina de Turing $X$ que usa
       o algoritmo $A$ com entradas $R(M_i)$ e $R(M_i)$; a sa\'{\i}da de $X$
       \'e o inverso da de $A$: se $M_i$ aceita $R(M_i)$, $X$ rejeita, e se
       $M_i$ rejeita $R(M_i)$, $X$ aceita. Observe, ent\~ao que:
       \[M_i \mbox{\it  aceita } R(M_i) \mbox{\it  se, e somente se, } X
         \mbox{\it  n\~ao aceita } R(M_i)\mbox{.}\]
       Portanto, a m\'aquina $X$ n\~ao pode ser nenhum dos dispositivos $M_i$,
       porque sen\~ao ter-se-ia que $X$ aceita $R(X)$ se, e somente se, $X$
       n\~ao aceita $R(X)$.
       Absurdo! Logo, nem toda linguagem recursiva \'{e} aceita por algum
       dispositivo em {\cal C}.
       
 \item {\it Seja $u\rightarrow v$ uma regra monot\^{o}nica. Construa uma
       seq\"u\^{e}ncia de regras monot\^{o}nicas, cada uma com lado direito de
       tamanho 2 ou menos, que defina a mesma transforma\c{c}\~{a}o que
       $u\rightarrow v$.}
       
       Seja $u=x_1x_2\ldots x_n$ e $v=y_1y_2\ldots y_k$, $k>2$ e $k\geq n$. Ent\~ao a
       seguinte seq\"u\^encia de regras defina a mesma transforma\c{c}\~{a}o que
       $u\rightarrow v$, onde $X_1$, $X_2$, \ldots, $X_{k-1}$ s\~ao {\it
       vari\'aveis novas\/}:
       
       $x_1x_2 \,\,\rightarrow\,\, y_1X_1$ \\
       $X_1x_3 \,\,\rightarrow\,\, y_2X_2$ \\
       $X_2x_4 \,\,\rightarrow\,\, y_3X_3$ \\

       \hspace*{5mm} $\vdots$

       terminando em $X_{n-2}x_n \,\,\rightarrow\,\, y_{n-1}y_n$, se $n=k$; caso
       contr\'ario, ao inv\'es desta \'ultima, tem-se as seguintes regras:
       
       $X_{n-2}x_n \,\,\rightarrow\,\, y_{n-1}X_{n-1}$ \\
       $X_{n-1}x_{n+1} \,\,\rightarrow\,\, y_nX_n$ \\
       $X_n \,\,\rightarrow\,\, y_{n+1}X_{n+1}$ \\

       \hspace*{5mm} $\vdots$
       
       $X_{k-2} \,\,\rightarrow\,\, y_{k-1}y_k$
              
 \item {\it Construa uma seq\"u\^{e}ncia de regras sens\'{\i}veis ao contexto
       $uAv\rightarrow uwv$ que defina a mesma transforma\c{c}\~{a}o que a regra
       monot\^{o}nica $AB\rightarrow CD$. ({\em Sugest\~{a}o\/}: Uma
       seq\"u\^{e}ncia de 3 regras, cada uma com os lados esquerdo e direito de
       tamanho 2, \'{e} suficiente.)}
       
       Uma solu\c c\~ao \'e introduzir uma {\it vari\'avel nova\/} $X$, e
       substituir $AB\rightarrow CD$ por $AB\rightarrow AX$, $AX\rightarrow CX$
       e $CX\rightarrow CD$. Outra solu\c c\~ao \'e substituir por
       $AB\rightarrow XB$, $XB\rightarrow XD$ e $XD\rightarrow CD$.
       
 \item {\it Use os resultados dos dois exerc\'{\i}cios anteriores para provar
       que toda linguagem sens\'{\i}vel ao contexto \'{e} gerada por uma
       gram\'{a}tica na qual cada regra tem a forma $uAv\rightarrow uwv$, onde
       $w\in (\Sigma\cup V)^+$ e $u,v\in (\Sigma\cup V)^*$.}
       
       Seja $L$ uma linguagem sens\'{\i}vel ao contexto. Por defini\c c\~ao,
       existe gram\'{a}tica sens\'{\i}vel ao contexto que gera $L$. Assim, seja
       uma gram\'{a}tica sens\'{\i}vel ao contexto, $G$, tal que $L(G)=L$.
       Aplicando-se o resultado da quest\~ao 4, constr\'oi-se uma gram\'atica $G'$,
       equivalente a $G$, cujas regras s\~ao da forma $u\rightarrow v$, onde
       $|v|\leq 2$ e $|u|\leq |v|$. Em seguida, aplicando-se o resultado da
       quest\~ao 5, constr\'oi-se uma gram\'atica $G''$, equivalente a $G'$ (e,
       portanto, equivalente a $G$), cujas regras s\~ao da forma
       $uAv\rightarrow uwv$, como requerido.
       
 \item {\it Construa um aut\^{o}mato linear limitado que aceite a linguagem
       \[\{a^{n!} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\] ({\em Sugest\~{a}o\/}:
       divida o {\em string\/} de entrada por 2, 3, 4, \ldots.)}

       Esbo\c co do ALL para $\{a^{n!} \,\,\,|\,\,\, n\geq 0\}$:

       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item se a fita tem apenas 1 $a$, pare e aceite;
        \item se o n\'umero de $a$'s n\~ao for divis\'{\i}vel por 2, pare e
              rejeite;
        \item apague a segunda metade da fita e escreva um $X$ na \'ultima
              posi\c c\~ao;
        \item se a fita tem apenas 1 $a$, pare e aceite;
        \item seja $n$ o n\'umero de $X$'s e $k$ o n\'umero de $a$'s; se
              $k$ n\~ao for m\'ultiplo de $n+2$, pare e rejeite;
        \item apague os \'ultimos $(n+1)/(n+2)$ $a$'s e escreva mais um $X$ no
              final da fita; volte ao passo (4).
       \end{list}

\end{enumerate}

\end{document}
