\documentclass[11pt, a4paper]{report}

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

\newcounter{conta}

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

\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. Se a palavra de entrada for $\lambda$, a MT dever\'a escrever
       {\tt 0}.

 \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 construir:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item uma MT que reconhece por parada em estado final equivalente a uma
              que reconhece por estado final;
        \item uma MT que reconhece por estado final equivalente a uma que
              reconhece por parada;
        \item uma MT que reconhece por parada equivalente a uma MT que
              reconhece por parada em estado final.
       \end{list}

 \item Fa\c ca uma MT que reconhe\c ca a linguagem:
       \[\{{\tt 0}^{k_0}{\tt 1}{\tt 0}^{k_1}{\tt 1}
       \ldots{\tt 0}^{k_n}{\tt 1}\,\,|\,\,n\in\mbox{\bf N} \mbox{ e }
       0<k_0<k_1<\cdots<k_n\}\mbox{.}\]
       Use uma fita s\'o para assegurar a restri\c c\~ao $0<k_0<k_1<\cdots<k_n$.

 \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 Seja um APN com duas pilhas, como mostrado no Exerc\'{\i}cio 11 da
       Se\c c\~ao~3.6, p\'agina 208 do livro texto. Mostre que esse tipo de
       m\'aquina reconhece a classe das LREs. {\em Dica\/}: Para simular
       uma MT por meio de um APN com duas pilhas, use uma pilha para conter
       $x^R$ e outra para $ay$, quando a configura\c c\~ao instant\^anea da MT
       for $[e,x\underline{a}y]$.

 \item Construa uma gram\'atica irrestrita (GI) que gere a linguagem
       \[\{{\tt a}^{m}{\tt b}^n{\tt a}^{m}{\tt b}^n \,|\, m,n\geq 0\}\mbox{.}\]
       Procure obter uma GI com um n\'umero m\'{\i}nimo de regras.

 \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 e sob fecho de
       {\em Kleene\/} por meio de MTs. {\em Dica\/}: Use {\em n\~ao\/}
       determinismo.

\end{enumerate}

\end{document}



