\documentclass[12pt,a4paper]{report}

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

\newcounter{conta}

\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \\ 
\noindent {\bf Trabalho especial} \hfill Entrega: 13/11/2004

\vspace*{5mm}
Fa\c ca um programa que, recebendo como entrada um conjunto finito de palavras,
construa um AFD m\'{\i}nimo\footnote{AFD com o menor n\'umero estados poss\'{\i}vel.}
que reconhe\c ca a linguagem constitu\'{\i}da por tais palavras. O programa
dever\'a implementar o seguinte algoritmo:
 \begin{tabbing}
  xxxx\=xxx\=xxx \kill \\
  \>$M\leftarrow$ AFD m\a'{\i}nimo que aceita $\emptyset$; \\
  \>{\bf enquanto} houver palavras a ler {\bf fa\c ca} \\
  \>   \> leia $w$; \\
  \>   \> $M\leftarrow$ AFD m\a'{\i}nimo que aceita $L(M)\cup\{w\}$ \\
  \>{\bf fimenquanto}; \\
  \>retorne $M$. \\
 \end{tabbing}

Dever\'a ser entregue um algoritmo, em alto n\'{\i}vel (como os da apostila),
que mostre como \'e feita a modifica\c c\~ao de um AFD m\'{\i}nimo para que
ele reconhe\c ca mais uma palavra (ou seja, como \'e feita a atribui\c c\~ao
``$M\leftarrow$ AFD m\a'{\i}nimo que aceita $L(M)\cup\{w\}$'' do algoritmo acima).

Quanto ao programa, dever\'a ser feita uma apresenta\c c\~ao do mesmo para o
professor em hor\'ario e dia a combinar, tendo o dia 13/11/2004 como limite
m\'aximo. A apresenta\c c\~ao dever\'a conter elementos suficientes para convencer,
no prazo m\'aximo de 15 minutos, quanto ao perfeito funcionamento do programa!
Nenhum documento dever\'a ser entregue relativo ao programa.

O algoritmo e a apresenta\c c\~ao do programa n\~ao ser\~ao aceitos ap\'os
13/11/2004, em hip\'otese alguma. Cada um vale 2 pontos.

\end{document}
