\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Oitava Lista de Exerc\'{\i}cios} \hfill Data de entrega: 27/06/2000

\begin{enumerate}
 \item Mostre que as seguintes linguagens n\~ao s\~ao livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\{w\in\{\verb+0+,\verb+1+,\verb+2+\}^*\,\,|\,\, w$ tem n\'umero igual de \verb+0+'s, \verb+1+'s e
               \verb+2+'s$\}$
         \item $\{xx^Rx\,\,|\,\, x\in\{\verb+0+,\verb+1+\}^*\}$
       \end{list}

 \item Mostre que a classe das linguagens livres do contexto \'e fechada sob reverso.

 \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 ${\cal P}(E\times\Gamma^*\times\Gamma^*)$.
         \end{itemize}
         Uma transi\c c\~ao neste tipo de aut\^omato manipula duas pilhas si\-mul\-ta\-nea\-men\-te. 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 Construa uma m\'aquina de Turing que transforme palavras $w$ de $\{\verb+0+,\verb+1+\}^*,$ de tamanho 8, em
        palavras $wd$ ($d\in\{\verb+0+,\verb+1+\}$), de tamanho 9, de forma que o n\'umero de \verb+1+'s em $wd$
        \'e \'{\i}mpar (paridade \'{\i}mpar).

 \item Construa m\'aquinas de Turing padr\~ao para:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n>k\}$
         \item $\{w\in\{\verb+0+,\verb+1+,\verb+2+\}^*\,\,|\,\, w$ tem n\'umero igual de \verb+0+'s, \verb+1+'s e
               \verb+2+'s$\}$
         \item $\{xx^Rx\,\,|\,\, x\in\{\verb+0+,\verb+1+\}^*\}$
        \end{list}

 \item Construa m\'aquinas de Turing de v\'arias fitas (2 ou mais) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n>k\}$
        \item $\{xx^Rx\,\,|\,\, x\in\{\verb+0+,\verb+1+\}^*\}$
       \end{list}
       Escolha o n\'umero de fitas de forma a minimizar o n\'umero de transi\c c\~oes a efetuar no reconhecimento de
       uma palavra.

 \item Construa uma m\'aquina de Turing de duas fitas para
       \[\verb+0+\verb+1+^{n_1}\verb+0+\verb+1+^{n_2}\ldots\verb+0+\verb+1+^{n_k}\,\,|\,\, k>0 \mbox{ e }
         n_1<n_2<\cdots <n_k\}\mbox{.}\]

 \item Construa uma m\'aquina de Turing n\~ao determin\'{\i}stica de duas fitas para
       $\{x\verb+c+y\,\,|\,\, |x|=|y| \mbox{ e } x,y\in\{\verb+a+,\verb+b+\}^*\}$. Uma computa\c c\~ao com entrada $w$
       deve terminar ap\'os, no m\'aximo, $|w|+2$ transi\c c\~oes.

 \item Mostre que as linguagens recursivas s\~ao fechadas sob complementa\c c\~ao, uni\~ao e interse\c c\~ao.

 \item Mostre que uma linguagem $L$ \'e recursiva se, e somente se, $L$ e $\overline{L}$ s\~ao recursivamente
       enumer\'aveis.

\end{enumerate}


\end{document}



