\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\setlength{\textheight}{250mm}

\newcounter{conta}

\begin{document}
 
\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} -- Turmas F e N \hfill 02/07/2009

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos, menos a \'ultima, que vale 3.

\vspace*{2mm}
\begin{enumerate}
 \item Seja o seguinte diagrama de estados de uma MT com alfabeto de entrada $\{{\tt a},{\tt b}\}$:
       \begin{center} \small
       \begin{picture}(110,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir](1)(20,10){1}
        \node(2)(45,10){2}
        \node[Nmarks=r](3)(70,10){3}

        \drawedge[curvedepth=0](1,2){${\tt a}/\sqcup\;{\tt D}$}
        \drawedge[curvedepth=0](2,3){${\tt b}/\sqcup\;{\tt D}$}
        \drawloop[loopangle=0](3){\shortstack{$\sqcup/\sqcup\;{\tt D}$\\${\tt a}/\sqcup\;{\tt D}$}}
       \end{picture}
       \end{center}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Para quais palavras essa MT entra em \textit{loop\/}?
        \item Descreva a linguagem que ela reconhece por meio de uma express\~ao regular.
        \item Construa uma MT equivalente que nunca entre em \textit{loop}.
       \end{list}

 \item Mostre como obter, a partir de uma MT padr\~ao (a que definimos inicialmente nas
       aulas e no livro-texto) uma MT equivalente com um \'unico estado final. Ou seja, dada
       uma MT $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$, como s\~ao $E'$, $\Gamma'$,
       $\delta'$ e $f$ para que $M'=(E',\Sigma,\Gamma',\langle,\sqcup,\delta',i,\{f\})$ seja
       tal que $L(M')=L(M)$?

 \item Construa uma gram\'atica irrestrita que gere $\{{\tt a}^n{\tt b}^{k}{\tt a}^n\,|\,k>n\}$.
       Caso a gram\'atica seja sens\'{\i}vel ao contexto, voc\^e ganha mais um ponto.

 \item Responda sim ou n\~ao. Para cada resposta certa voc\^e ganha meio ponto
       e para cada resposta errada perde meio ponto:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item MTs determin\'{\i}sticas e n\~ao determin\'{\i}sticas t\^em o mesmo poder computacional.
        \item Toda linguagem \'e enumer\'avel (finita ou infinita), mas nem toda linguagem \'e recursivamente
              enumer\'avel. 
        \item O complemento de uma linguagem recursiva pode n\~ao ser recursiva.
        \item Seja $L$ uma linguagem recursivamente enumer\'avel n\~ao  recursiva. Toda MT que
              reconhe\c{c}a $L$ entra em \textit{loop\/} para alguma palavra de entrada.
        \item As classes de linguagens vistas (regulares, livres do contexto, sens\'{\i}veis
              ao contexto, recursivas e recursivamente enumer\'aveis) s\~ao todas fechadas
              sob interse\c{c}\~ao.
        \item Uma m\'aquina de Turing n\~ao determin\'{\i}stica com duas fitas tem um poder computacional
              maior que o de uma determin\'{\i}stica de uma fita s\'o.
       \end{list}
\end{enumerate}
\end{document}
