\documentclass[12pt, a4paper]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas ne-nhum re-gu-lar}
\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{1}^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Lista de Exerc\'{\i}cios} \hfill Data de entrega: 05/07/2002

\begin{enumerate}
 \item Construa uma MT que, recebendo como entrada um n\'umero na nota\c c\~ao bin\'aria,
       some 1 ao mesmo e retorne o cabe\c cote para a posi\c c\~ao inicial.

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

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) {\em n\~ao
       determin\'{\i}sticas\/} que reconhe\c cam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{xww^Ry\,\,|\,\, x,y,w\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|\geq |y|\}$
        \item $\{\verb+a+^n\,\,|\,\, n \mbox{ n\~ao \'e primo}\}$
       \end{list}

 \item Seja uma MT que, em cada transi\c c\~ao s\'o pode escrever um s\'{\i}mbolo ou
       mover o cabe\c cote, mas n\~ao ambos. Fa\c ca uma defini\c c\~ao formal deste
       tipo de m\'aquina. Depois mostre que as m\'aquinas desse tipo reconhecem as
       LRE's.

 \item Construa uma GSC que gere e um ALL que reconhe\c ca a linguagem
       \[\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\,m>n>k\}\mbox{.}\]

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

 \item Sejam $L$ uma LRE e $R$ uma linguagem recursiva.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $L-R$ \'e uma LRE.
        \item $L-R$ \'e recursiva?
        \item $R-L$ \'e LRE?
       \end{list}

 \item Mostre que existe algoritmo que, dada uma MT $M$, determina se $M$ escreve
       algum s\'{\i}mbolo diferente de branco, para a entrada $\lambda$.

 \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 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\'atica regular arbitr\'{a}ria e $G_2$ uma GLC arbitr\'{a}ria.
       O problema de determinar se $L(G_1)\cap L(G_2)=\phi$ \'e decid\'{\i}vel?

 \item Prove que n\~{a}o existe algoritmo que determine se a interse\c{c}\~{a}o das
       linguagens geradas por duas GLC's cont\'{e}m uma infinidade de elementos.

\end{enumerate}

\end{document}
