\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 2005 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
{\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 22/06/05

\begin{enumerate}

 \item Construa uma MT com alfabeto de entrada $\{{\tt 0},{\tt 1}\}$ que desloque
       a palavra de entrada 1 s\'{\i}mbolo para a direita.

 \item Construa uma MT com alfabeto de entrada $\{{\tt a},{\tt b},{\tt c},{\tt l}\}$ que pare se,
       e somente se, a palavra de entrada n\~ao come\c ca com ${\tt bla}$.

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^{n}\verb+b+^n \,|\, n\geq 0\}$.
        \item $\{\verb+a+^{n}\verb+b+^n\verb+c+^{n}\verb+d+^n \,|\, n\geq 0\}$.
        \item $\{\verb+a+^{m}\verb+b+^n \,|\, m\not=n\}$.
        \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 um m\'{\i}nimo de transi\c c\~oes poss\'{\i}vel.

 \item Seja a linguagem $L$, de alfabeto $\{{\tt a},{\tt [},{\tt ]},{\tt +}\}$,
       definida recursivamente assim:
       \begin{itemize}
        \item ${\tt a}\in L$;
        \item se $x\in L$ e $y\in L$, ent\~ao $x{\tt +}y\in L$;
        \item se $x\in L$, ent\~ao ${\tt [} x {\tt ]}\in L$ e $x {\tt ]}\in L$.
       \end{itemize}
       Construa uma MT, de um tipo que d\^e menos trabalho, que reconhe\c ca
       tal linguagem.

 \item Mostre como simular uma MT padr\~ao por meio de uma MT em que a
       fun\c c\~ao de transi\c c\~ao \'e da forma
       $\delta:E\times\Gamma\rightarrow E\times(\Gamma\cup\{E,D\})$, ou seja,
       uma transi\c c\~ao poder ser:
       \begin{itemize}
        \item $\delta(e,a)=[e',b]$, $b\in \Gamma$ (no estado $e$ se o s\'{\i}mbolo
              de entrada for $a$, escreva $b$ e v\'a para o estado $e'$);
        \item $\delta(e,a)=[e',d]$, $d\in\{E,D\}$ (no estado $e$ se o s\'{\i}mbolo
              de entrada for $a$, mova o cabe\c cote de leitura segundo $d$ e
              v\'a para o estado $e'$).
       \end{itemize}

 \item Construa gram\'aticas irrestritas que gerem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\, m<n<k\}$.
        \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 Construa uma GSC que gere e um ALL que reconhe\c ca a linguagem
       \[\{\verb+a+^n\verb+b+^{n+1}\verb+c+^{n+2}\,\,|\,\, n\geq 0\}\mbox{.}\]

 \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 $L\cup R$ pode ser recursiva, se $R$ \'e regular.
        \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}

\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.
