\documentclass[12pt, a4paper]{report}

 \addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1.0in}

\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 2004
 
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG
 
\noindent {\bf Trabalho Extra} \hfill Entrega: 09/07/2004

\vspace*{3mm}
\begin{enumerate}
 \item Fa\c ca um procedimento que, dado um AFD $M$, construa um AFD
       {\em m\'{\i}nimo\/} $M'$ equivalente. Para isto, use o algoritmo
       descrito no artigo:
       \begin{quote}
        Hopcroft, J.E. An $n\log n$ algorithm for minimizing the states in a
        finite automaton. In Z. Kohavi (ed.) {\em The Theory of Machines and
        Computations\/}, Academic Press, New York, 1971, pp. 189--196.
       \end{quote}
       Quase todos os livros citados no Plano de Curso apresentam tal
       algoritmo, como, por exemplo, Hopcroft, Motwani \& Ullman(2001)
       na p\'ag. 155, Hopcroft\& Ullman(1979) na p\'ag. 68, e Sudkamp(1997)
       na p\'ag. 182.
 \item Fa\c ca um programa que receba como entrada as linhas
       de uma tabela da verdade (em bin\'ario) e:
       \begin{itemize}
        \item Construa uma AFD do tipo ``\'arvore'' que reconhe\c ca as
              palavras em bin\'ario para as quais a f\'ormula
              \'e verdadeira (isto \'e, o valor \'e 1).
        \item Minimize o AFD.
        \item Exiba o AFD (no formato que achar melhor).
       \end{itemize}
\end{enumerate}

O trabalho vale 4 pontos: 2 pontos para o procedimento de minimiza\c c\~ao
e 2 para o resto.

Dever\~ao ser entregues \underline{diretamente para o monitor}
o c\'odigo fonte e o c\'odigo execut\'avel. Pode ser usada qualquer
linguagem de programa\c c\~ao.

\end{document}
