\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} \hfill 29/11/2006

\vspace*{3mm}

\noindent {\bf Cada uma das 5 quest\~oes a seguir vale 4 pontos e a \'ultima
vale 2 pontos.} Se voc\^e corria o risco de n\~ao tirar conceito A,
com esses 7 pontos extra n\~ao deve correr mais!

\vspace*{1mm}
\begin{enumerate}
 \item Seja a MT $M=(\{1,2\},\{{\tt 0},{\tt 1}\},\{{\tt 0},{\tt 1},\langle,\sqcup\},
       \langle,\sqcup,\delta,1,\{2\})$ com o diagrama de estados a seguir:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,30)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i](1)(50,10){1}
         \node[Nmarks=r](2)(80,10){2}

         \drawedge[curvedepth=4](1,2){${\tt 0}/{\tt 0}$ {\sf D}}
         \drawedge[curvedepth=4](2,1){\shortstack{${\tt 0}/{\tt 1}$ {\sf E} \\
                                                 ${\tt 1}/{\tt 0}$ {\sf E}}}
         \drawloop[loopangle=90, ELside=l](1){${\tt 1}/{\tt 1}$ {\sf D}}
        \end{picture}
       } \\

       Que linguagem \'e reconhecida por $M$? Expresse-a por
       meio de uma express\~ao regular. N\~ao precisa explicar como chegou \`a
       resposta. 

 \item Construa o diagrama de estados de uma MT que reconhe\c{c}a
       \[\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)=n_{\tt 1}(w)\}\mbox{.}\] 
       Dica: use uma fita para contar o n\'umero de {\tt 0}s (ou de {\tt 1}s).
       Lembre-se que a palavra de entrada vem na fita 1 e que as outras
       fitas (se houver) come\c{c}am em branco.

 \item Construa uma gram\'atica irrestrita (GI) que gere
       $\{{\tt 0}^n{\tt 1}^n{\tt 0}^n\,|\,n\geq 0\}$.

 \item Mostre como se pode obter uma GI $G'$ equivalente a uma GI $G$ que s\'o
       possua regras das formas:
       \begin{itemize}
        \item $u\,\rightarrow\, v$ tal que $|u|\leq |v|$;
        \item $A\,\rightarrow\, \lambda$, sendo $A$ uma vari\'avel.
       \end{itemize}

 \item Se uma linguagem \'e recursivamente enumer\'avel, mas n\~ao recursiva,
       o que se pode dizer de seu complemento? Justifique.

 \item Preencha o que est\'a vago no seguinte quadro (se quiser ficar com o enunciado
       ap\'os terminar a prova, copie o quadro na folha de respostas):
       \begin{center}
        \begin{tabular}{|c|c|c|} \hline
         \hspace*{8mm}{\em Linguagem}\hspace*{8mm} & {\em Reconhecedor}    & \hspace*{8mm}{\em Gram\'atica}\hspace*{8mm} \\ \hline\hline
              & aut\^omato finito                &             \\ \hline
              & aut\^omato de pilha              &             \\ \hline
              & aut\^omato linearmente limitado  &             \\ \hline
              & m\'aquina de Turing              &   \\ \hline
        \end{tabular}
       \end{center}
\end{enumerate}

\end{document}
 
