\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2006 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
{\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 04/07/06

\begin{enumerate}

 \item Construa uma MT com alfabeto de entrada $\{{\tt 0},{\tt 1}\}$ que apague
       todos os {\tt 0}s.

 \item Construa uma MT com alfabeto de entrada $\Sigma =$ conjunto de todas as
       letras mai\'usculas da lingua portuguesa, que pare se,
       e somente se, a palavra de entrada n\~ao come\c ca com ${\tt LOOP}$.

 \item Construa MT's para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^{n}\verb+b+^n\verb+c+^{n} \,|\, n\geq 0\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^* \,|\, n_{\tt a}(w)\not=n_{\tt b}(w)\}$.
        \item $\{{\tt a}^n \,|\, n \mbox{ \'e maior que 1 e n\~ao \'e primo}\}$.
        \item $\{xx^Ry \,|\, x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e } |x|>|y|\}$.
       \end{list}
       Procure obter uma m\'aquina bem concisa. Para isso, use v\'arias fitas e
       n\~ao determinismo, quando apropriado.

 \item Seja a linguagem $L=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|$ em qualquer
       prefixo de $w$, o n\'umero de {\tt a}s \'e maior ou igual ao de {\tt b}s
       $\}$. Construa uma MT, de um tipo que d\^e menos trabalho, que reconhe\c ca
       $L$.

 \item Mostre como uma MT n\~ao determin\'{\i}stica que tem um conjunto de estados
       iniciais pode ser simulada mediante uma MT n\~ao determin\'{\i}stica com
       um \'unico estado inicial.

 \item Construa gram\'aticas irrestritas que gerem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^k\verb+b+^n\verb+a+^k\verb+b+^n\,\,|\,\, k,n\geq 0\}$.
        \item $\{www\,\,|\,\,w\in\{\verb+0+,\verb+1+\}^*\}$.
       \end{list}

 \item Mostre que para toda gram\'atica irrestrita existe uma equivalente
       em que cada regra tem o lado direito maior ou igual ao lado esquerdo
       ou \'e regra $\lambda$.

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L\cup F$ n\~ao \'e recursiva, se $F$ \'e finita.
        \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 as LREs s\~ao fechadas sob concatena\c c\~ao. {\em Dica:} use
       n\~ao determinismo.
\end{enumerate}

\end{document}



 \item Construa uma MT com alfabeto de entrada $\{\verb+0+,\verb+1+\}$, que interprete a
       palavra de entrada como a representa\c c\~ao bin\'aria de um n\'umero natural e
       determine a representa\c c\~ao un\'aria de tal n\'umero. Pode usar qualquer modelo
       de MT; em particular, pode usar uma fita s\'o para conter o resultado.

 \item Construa uma MT com fita ilimitada em ambas as dire\c c\~oes que, come\c cando a
       fita com duas c\'elulas contendo o s\'{\i}mbolo \verb+1+ e o resto branco, determine
       se o n\'umero de brancos entre os dois \verb+1+'s \'e \'{\i}mpar, e, neste caso,
       pare em estado de aceita\c c\~ao. Observe que os dois s\'{\i}mbolos referidos pode
       estar em {\em qualquer lugar\/} da fita.
