\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 Quarta Lista de Exerc\'{\i}cios} \hfill Data de entrega: 14/12/2000

\section{M\'aquinas de Turing}

\vspace*{2mm}

\begin{enumerate}
 \item Construa uma m\'aquina de Turing (MT) padr\~ao que reconhe\c ca a linguagem
       $\{xx\,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$.
       Mostre como construir MT's padr\~oes para linguagens da forma
       $\{x^k\,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$,
       sendo $k$ uma constante maior que zero.

 \item Seja uma MT $M=(E,\Gamma,\Sigma,\delta,i,F)$ sendo $\delta$ uma fun\c c\~ao de
       $E\times\Gamma$ para $E\times\Gamma\times\{\mbox{D},\mbox{I}\}$. Ou seja, $M$ \'e uma MT
       padr\~ao cujo cabe\c cote pode apenas se mover para a direita (D) ou ficar im\'ovel (I)
       em cada transi\c c\~ao. $M$ reconhece apenas linguagens regulares, ou existe alguma linguagem n\~ao
       regular que $M$ reconhece?

 \item Construa uma MT com fita ilimitada em ambas as dire\c c\~oes que, come\-\c can\-do
       a fita com duas c\'elulas contendo o s\'{\i}mbolo \verb+0+ (e o resto branco), determine se o
       n\'umero de brancos entre os dois \verb+0+'s \'e \'{\i}mpar (neste caso, a m\'aquina p\'ara em
       estado de aceita\c c\~ao). Observe que os dois s\'{\i}mbolos referidos podem estar em {\em qualquer
       lugar\/} na fita.

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq 0\}$
        \item $\{\verb+0+^{n!}\,\,|\,\, n\geq 0\}$
      \end{list}

 \item Construa MT's n\~ao determin\'{\i}sticas que reconhe\c cam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{xx\,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{xww^Ry\,\,|\,\, x,y,w\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|\geq |y|\}$
      \end{list}

 \item Descreva uma MT que resolva o problema de decis\~{a}o:
       \begin{quote}
        Dada uma MT arbitr\'{a}ria $M$ e uma palavra de entrada $w$, ir\'{a} a computa\c{c}\~{a}o de
        $M$ com entrada $w$ parar em menos de 1000  transi\c{c}\~{o}es?
       \end{quote}
       
 \item Mostre que se o problema da parada fosse decid\'{\i}vel toda linguagem recursivamente
       enumer\'{a}vel seria recursiva.
              
 \item Prove que n\~{a}o existe algoritmo que determine se uma MT arbitr\'{a}ria ir\'{a} parar para
       {\em alguma\/} entrada.
       
 \item Prove que n\~{a}o existe algoritmo que determine se uma MT arbitr\'{a}ria ir\'{a} parar para
       {\em todas\/} as palavras de entrada.
       
 \item Prove que n\~{a}o existe algoritmo que receba como entrada uma MT $M=(E,\Gamma,\Sigma,\delta,i,F)$,
       um estado $e\in E$, e uma palavra $w\in\Sigma^*$, e determine se a computa\c{c}\~{a}o de $M$
       com entrada $w$ entra no estado $e$.

 \item Prove que n\~{a}o existe algoritmo que determine se $L(M)=\phi$, para uma MT arbitr\'{a}ria $M$.
       ({\em Sugest\~{a}o\/:} reduzir o problema da fita em branco a este.)
       
 \item Prove que o problema da correspond\^{e}ncia de Post para sistemas com alfabeto de um \'{u}nico
       s\'{\i}mbolo \'{e} decid\'{\i}vel.
       
 \item Sejam $G_1$ uma gram\'{a}tica regular arbitr\'{a}ria e $G_2$ uma gram\'{a}tica livre do contexto
       arbitr\'{a}ria. \'{E} decid\'{\i}vel o problema de determinar se $L(G_1)\cap L(G_2)=\phi$?
       
 \item Prove que n\~{a}o existe algoritmo que determine se a interse\c{c}\~{a}o das linguagens de duas
       gram\'{a}ticas livres do contexto cont\'{e}m uma infinidade de elementos.
       
 \item Prove que n\~{a}o existe algoritmo que determine se o complemento da linguagem de uma gram\'{a}tica
       livre do contexto cont\'{e}m uma infinidade de elementos.
       
\end{enumerate}

\end{document}
