\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{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeiro Trabalho Prático} -- Turmas D e W\hfill {Entrega: 21/10/2012}

\section{Enunciado}
\noindent Faça um programa que receba como entrada dois AFDs $M_1$ e $M_2$ e determine se:
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item $L(M_1)$ e $L(M_2)$ são disjuntas.
 \item $L(M_1)\subseteq L(M_2)$.
 \item $L(M_2)\subseteq L(M_1)$.
 \item $L(M_1)\subset L(M_2)$.
 \item $L(M_2)\subset L(M_1)$.
 \item $L(M_1) = L(M_2)$.
\end{list}
Para cada resposta ``não'' o programa deve apresentar um contra-exemplo (caso exista), ou seja, uma palavra $x$ tal que, para cada um dos casos acima:
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item $x\in L(M_2)\cap L(M_1)$.
 \item $x\in L(M_1)$ e $x\not\in L(M_2)$.
 \item $x\in L(M_2)$ e $x\not\in L(M_1)$.
 \item $x\in L(M_1)$ e $x\not\in L(M_2)$ ou então dizer que $L(M_1) = L(M_2)$.
 \item $x\in L(M_2)$ e $x\not\in L(M_1)$ ou então dizer que $L(M_2) = L(M_1)$.
 \item $x\in L(M_1)$ e $x\not\in L(M_2)$ ou então $x\in L(M_2)$ e $x\not\in L(M_1)$.
\end{list}

\section{Sugestões}

\noindent Sugiro implementar rotinas para:
\begin{itemize}
 \item Fazer o \emph{produto} de dois AFDs. O produto de dois AFDs $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e $M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$, é um autômato da forma
	      $M_p=(E1\times E_2,\Sigma,\delta_p,[i_1,i_2])$ em que: $$\delta_p([e_1,e_2],a)=[e_1',e_2'] \mbox{ sse } \delta_1(e_1,a)=e_1' \mbox{ e } \delta_2(e_2,a)=e_2'\mbox{.}$$
 \item Eliminar do produto todo estado \emph{inútil}. Um estado $e$ de $M$ é \emph{útil} sse existe caminho (no diagrama de estados) do estado inicial de $M$ a $e$. 
\end{itemize}
Assim, por exemplo, $L(M_1)\subset L(M_2)$ se e somente se valem as duas condições:
\begin{enumerate}
 \item para todo $[e_1,e_2]\in E_1\times E_2$ de $M_p$ \emph{que seja útil}, $e_1\in F_1 \rightarrow e_2\in F_2$; e
 \item existe $[e_1,e_2]\in E_1\times E_2$ de $M_p$ \emph{que é útil} e $e_1\not\in F_1$ e $ e_2\in F_2$.
\end{enumerate}
E $L(M_1) = L(M_2)$ sse para todo $[e_1,e_2]\in E_1\times E_2$ de $M_p$ \emph{que seja útil}, $e_1\in F_1 \leftrightarrow e_2\in F_2$.

\pagebreak

\section{Informações adicionais}

\begin{enumerate}
 \item O trabalho é individual.
 \item Pode usar a linguagem de programação de sua preferência.
 \item Os dados para teste do programa serão passados, oportunamente, no Moodle, via arquivos do tipo texto. Alguma coisa do tipo, para cada AFD:
       \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 por volta do dia 4/10 em horário diverso do das aulas normais. Fique atento para a definição do horário dessa aula, o qual será postado no Moodle e na
       página do professor. Nesta aula, será explicado, inclusive, como será feita a apresentação do trabalho (com execução do programa e entrevista).
\end{enumerate}


\end{document}
