\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} -- Turma W \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 0},{\tt 1},{\tt 2}\}$:
       \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[Nmarks=r](2)(45,10){2}
%        \node[Nmarks=r](3)(70,10){3}

        \drawedge[curvedepth=0](1,2){${\tt 0}/\sqcup\;{\tt D}$}
%        \drawedge[curvedepth=0](2,3){${\tt 1}/\sqcup\;{\tt D}$}
        \drawloop[loopangle=0](2){\shortstack{$\sqcup/\sqcup\;{\tt D}$\\${\tt 2}/\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 Existe algoritmo que, dada uma MT $M$, obtenha uma MT $M'$ equivalente que sempre pare?
       Justifique.

 \item Construa uma gram\'atica irrestrita que gere $\{{\tt a}^{n}{\tt b}^n{\tt c}^{k}\,|\,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 Todo subconjunto de linguagem recursivamente enumer\'avel \'e
              recursivamente enumer\'avel.
        \item Se $R$ \'e regular e $L$ da classe $T$, sendo $T$ regular, livre do contexto,
              sens\'{\i}vel ao contexto, recursiva ou recursivamente enumer\'avel, ent\~ao
              $L\cup R$ \'e do tipo $T$.
        \item Se $L$ n\~ao \'e recursiva, $\overline{L}$ tamb\'em n\~ao \'e.
        \item Por defini\c{c}\~ao, as linguagens recursivas s\~ao aquelas que podem ser geradas
              por gram\'aticas sens\'{\i}veis ao contexto.
        \item Se $L$ n\~ao \'e recursivamente enumer\'avel, $\overline{L}$ tamb\'em
              n\~ao \'e.
        \item Gram\'aticas irrestritas geram linguagens recursivamente enumer\'aveis.
       \end{list}
\end{enumerate}
\end{document}
