\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{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova/Especial} \hfill 26/06/2007

\vspace*{1mm}

\noindent {\bf Cada uma das 5 quest\~oes a seguir vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}
 \item Construa o diagrama de estados de uma MT padr\~ao com alfabeto de
       entrada $\Sigma =\{{\tt a},{\tt e},{\tt i},{\tt o},{\tt u}\}$
       que reconhe\c ca $\{w\in\Sigma^*\,|\, w$ n\~ao cont\'em {\tt oo}$\}$,
       usando o crit\'erio de reconhecimento {\em por parada}. Ou seja,
       a MT deve parar se, e somente se, a palavra de entrada n\~ao tiver
       {\tt oo} como subpalavra.

 \item Construa o diagrama de estados de uma MT de duas fitas n\~ao
       determin\'{\i}stica que reconhe\c ca $\{xx^R \,|\, x\in\{\verb+0+,\verb+1+\}^*\}$.
       Quando a palavra de entrada for da forma $xx^R$, a computa\c c\~ao
       de aceita\c c\~ao deve copiar $x$ na fita 2 e compar\'a-la com
       o restante da fita de entrada.

 \item Mostre como uma MT n\~ao determin\'{\i}stica que tem um conjunto de estados
       iniciais pode ser simulada mediante uma MT n\~ao determin\'{\i}stica com
       um \'unico estado inicial. (Suponha que o cabe\c cote pode ficar im\'ovel
       em uma transi\c c\~ao.)

 \item Construa uma gram\'atica irrestrita que gere $\{w\overline{w}\,|\,w\in\{\verb+0+,\verb+1+\}^*$
       e $\overline{w}$ \'e o complemento de $w\}$. (O complemento de $w$ \'e o resultado de
       substituir em $w$ cada {\tt 0} por {\tt 1} e cada {\tt 1} por {\tt 0}.)

 \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
         regular         &                       &             \\ \hline
                         & aut\^omato de pilha  &             \\ \hline
                         & aut\^omato linearmente limitado  &             \\ \hline
                         &                       & irrestrita  \\ \hline
        \end{tabular}
       \end{center}
       Existe algum outro tipo de linguagem que n\~ao esteja mencionado no
       quadro acima? Se sim, qual?
\end{enumerate}


\end{document}
 
