\documentclass[12pt, a4paper]{report}

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

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Exame Especial} \hfill 12/07/2005

\vspace*{3mm}
\noindent {\bf Cada quest\~ao vale 20 pontos.}

\vspace*{2mm}
\begin{enumerate}
 \item Fa\c ca aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:
       \[X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w| \mbox{ \'e par}\} \mbox{ e }
         Y=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt 11}}\}\mbox{.}\]
       Bastam apenas os \underline{diagramas
       de estados}. Em seguida, obtenha o produto dos dois AFD's e explicite
       que estados finais ele deve ter para reconhecer
       $X\cap Y$ e $X\cup Y$.

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}'s em
                   $w$ \'e par}\}$.
        \item $\{wxw^R\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{{\tt b}\}^*\}$.
       \end{list}

 \item Construa um aut\^omato finito n\~ao determin\'{\i}stico para a linguagem a
       seguir, com o {\em menor n\'umero de estados e de transi\c c\~oes\/}
       que conseguir (use v\'arios estados iniciais):
       \begin{quote}\em
        o conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$
        em que o \'ultimo s\'{\i}mbolo n\~ao ocorre anteriormente.
       \end{quote}
       Na constru\c c\~ao de um aut\^omato finito determin\'{\i}stico
       equivalente, utilizando-se o m\'etodo visto
       no curso, qual seria o estado inicial? Quais seriam seus sucessores?

 \item Construa um aut\^omato com pilha que reconhe\c ca
        $\{(\verb+01+)^n\verb+1+(\verb+10+)^n\,\,|\,\,n\geq 0\}$.

 \item Construa uma MT com alfabeto de entrada $\{{\tt 0},{\tt 1}\}$ que desloque
       a palavra de entrada 1 s\'{\i}mbolo para a direita.

\end{enumerate}
\end{document}
