\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
%\setlength{\topmargin}{1.5cm}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 26/11/2009

\begin{enumerate}

 \item Construa uma MT que, recebendo como entrada uma palavra $w\in\{{\tt 0},{\tt 1}\}^*$, escreva $w^R$
       no seu lugar e retorne o cabe\c cote para a posi\c c\~ao inicial.

 \item Crie uma MT que reconhe\c ca a linguagem denotada pela ER $a(a+b)^*$,
       assumindo que o alfabeto \'e $\{{\tt a},{\tt b}\}$, de forma que ela
       tenha:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item um n\'umero m\'{\i}nimo de estados;
        \item um n\'umero m\'{\i}nimo de transi\c c\~oes.
       \end{list}

 \item Mostre como, dada uma MT $M$ com reconhe\c{c}imento padr\~ao (parada em estado final),
       obter uma MT $M'$ que reconhe\c{c}a $L(M)$ por parada. Exemplifique com uma MT padr\~ao
       que reconhe\c{c}a $a(a+b)^+$.
 
 \item Fa\c ca uma MT que reconhe\c ca a linguagem $\{wxw\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item de duas fitas determin\'{\i}stica;
        \item de duas fitas n\~ao determin\'{\i}stica.
       \end{list}

 \item Seja uma MT $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,\{f\})$ cuja
       \'unica diferen\c ca com rela\c c\~ao a uma MT-padr\~ao \'e que ela
       tem apenas um estado final. Suponha que a linguagem reconhecida por $M$ seja
       \[\{w\in\Sigma^*\,\,|\,\, [i,\langle\underline{w}]\stackrel{*}{\vdash}
         [f,x\underline{a}y]\}\mbox{.}\]
       Ou seja, para qualquer $w\in\Sigma^*$ $M$ reconhece $w$ se, e somente se,
       $M$ atinge o estado $f$ ao processar $w$.
       Mostre que qualquer linguagem recursivamente enumer\'avel pode ser
       reconhecida por uma MT desse tipo.

 \item Construa gram\'aticas irrestritas (GIs) que gerem as linguagens:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^{m}{\tt b}^n{\tt a}^{m}{\tt b}^n \,|\, m,n\geq 0\}$.
        \item $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.
       \end{list}

 \item Construa uma gram\'atica sens\'{\i}vel ao contexto (GSC) para a linguagem
       \[\{{\tt a}^m{\tt b}^n{\tt c}^k\,\,|\,\,m<n<k\}\mbox{.}\]
       Procure obter uma GSC com um n\'umero m\'{\i}nimo de regras.

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{\bf  \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 Mostre que as LREs s\~ao fechadas sob concatena\c c\~ao por meio de MTs.
       {\em Dica\/}: Use {\em n\~ao\/} determinismo.

 \item Seja $\Sigma=\{{\tt 0},{\tt 1}\}$. Considerando que o conjunto de todas as MTs de alfabeto de entrada
       $\Sigma$ \'e enumer\'avel, mostre que existe uma linguagem, subconjunto de $\Sigma^*$, que n\~ao \'e LRE.
       Para isso, use o argumento da diagonaliza\c c\~ao de Cantor (veja a p\'agina 25 do livro-texto).

\end{enumerate}

\end{document}
