\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 29/11/2006

\begin{enumerate}

 \item Construa uma MT padr\~ao com alfabeto de entrada $\{{\tt 0},{\tt 1}\}$
       que apague todos os {\tt 1}s e substitua todos os {\tt 0}s por
       {\tt 1}s (n\~ao importa onde termina o cabe\c{c}ote). Exemplo: se
       a fita contiver a entrada $<{\tt 0011010001}\sqcup\cdots$, no final
       dever\'a conter $<{\tt 111111}\sqcup\cdots$

 \item Construa uma MT padr\~ao que reconhe\c{c}a \underline{por parada}:
       \[\{w\in\{{\tt 1},{\tt 2},{\tt 3}\}^*\,|\, {\tt 12} \mbox{ n\~ao \'e
       subpalavra de $w$}\}\mbox{.}\] Procure usar o menos n\'umero de
       estados e transi\c{c}\~oes poss\'{\i}vel.

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

 \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 $\{{\tt 0}^{k}{\tt 1}^n{\tt 0}^{k}{\tt 1}^n \,|\, k,n\geq 0\}$.
        \item $\{ww^Rw\,|\,w\in\{{\tt 0},{\tt 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 utilizando
       MTs. {\em Dica:} use n\~ao determinismo.

 \item Mostre que as LREs s\~ao fechadas sob concatena\c c\~ao utilizando
       gram\'aticas irrestritas. {\em Dica:} $P\,\rightarrow\,P_1P_2$
       n\~ao funciona\ldots
\end{enumerate}

\end{document}
