\documentclass[12pt, a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}

\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeiro Trabalho Prático} -- Turma W\hfill {Entrega: 25/04/2013}

\section{Enunciado}
\noindent Faça um programa que, recebendo como entrada um AFD, determine um AFD mínimo equivalente. Deverá ser implementado o seguinte algoritmo:

{\sf
\begin{tabbing}
 xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\= \kill
 \> Entrada: um AFD $(E,\Sigma,\delta,i,F)$. \\
 \> Saída: AFD $(E',\Sigma,\delta',i',F')$. \\
 \> \textsl{conjunto de conjuntos de estados}: $R,S$; \\
 \> \textsl{conjunto de estados}: $C,Y,X$; \\
 \> \textsl{estado}: $e, d$; \\
 \> elimine todo estado alcançável a partir do estado inicial $i$; \\
 \> $R := \{E-F,F\}-\{\{\}\}$; \\
 \> {\bf repita} \\
 \> \> $S := R$; $R := \{\}$; \\
 \> \> {\bf para} cada $C\in S$ {\bf faça} \\
 \> \> \> {\bf repita} \\
 \> \> \> \> escolha $e$ de $C$; \\
 \> \> \> \> $Y := \{e\}$; \\
 \> \> \> \> L: {\bf para} cada $d\in C-\{e\}$ {\bf faça} \\
 \> \> \> \> \> {\bf para} cada $a\in\Sigma$ {\bf faça} \\
 \> \> \> \> \> \> seja $X\in S$ tal que $\delta(e,a)\in X$; \\
 \> \> \> \> \> \> {\bf se} $\delta(d,a)\not\in X$ {\bf então} {\bf continue} L {\bf fimse} \\
 \> \> \> \> \> {\bf fimpara}; \\
 \> \> \> \> \> $Y := Y\cup \{d\}$ \\
 \> \> \> \> {\bf fimpara}; \\
 \> \> \> \> $C := C-Y$; \\
 \> \> \> \> $R := R\cup \{Y\}$; \\
 \> \> \> {\bf até} $C=\{\}$ \\
 \> \> {\bf fimpara} \\
 \> {\bf até} $R=S$;\\
 \> $E' := S$; \\
 \> $\delta'$: para todo $C\in S$ e $a\in\Sigma$: \\
 \> \> $\delta'(C,a)=\mbox{ conjunto em $S$ que contém $\delta(e,a)$ para algum $a\in C$}$ \\
 \> $i' := \mbox{conjunto em } S \mbox{ que contém } i$; \\
 \> $F' := \{C\in S\,|\, C\subseteq F\}$; \\
\end{tabbing}
}


\pagebreak

\section{Informações adicionais}

\begin{enumerate}
 \item O trabalho é individual.
 \item Deve ser usada uma das linguagens: C, C++ ou Java.
 \item A entrada do programa é um arquivo texto contendo um AFD representado da seguinte forma:
       \begin{verbatim}
1 2 3 4 5 6 7 ; //estados
0 1 ; //alfabeto

2 3 , //transicoes (de 1, lendo 0, vai p/ 2 e de 1, lendo 1, vai p/ 3)
1 3 , // (de 2, lendo 0, vai p/ 1 e de 2, lendo 1, vai p/ 3)
4 3 ,
5 6 ,
5 7 ,
7 6 ,
5 7 ;

1 ;  //estado inicial
4 6 ; //estados finais
     \end{verbatim}
 \item Haverá uma aula para apresentação do trabalho no dia 09/04 às 19:50. Nesta aula, será explicado, inclusive, como será feita a apresentação do trabalho (com execução do programa e entrevista).
 \item O código fonte deverá ser entregue, via Moodle, até o dia 25/04/2012 às 23:55h.
 \item O trabalho deverá ser apresentado no dia 26/04/2012 às 17:00 (local a definir).
\end{enumerate}


\end{document}
