\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\begin{document}

\pagestyle{empty}

\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\em Fundamentos da Teoria da Computa\c{c}\~ao}
$\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2001 \\
Prof.: Newton Jos\'{e} Vieira \hfill Sala 4023/ICEx; e-mail: nvieira@dcc.ufmg.br
 
\noindent {\bf Primeiro Trabalho Pr\'atico}

\noindent {\bf Data de Entrega: 08/05/01}.

\vspace*{5mm}
Este trabalho \'e opcional, especialmente dirigido para aqueles que tenham interesse em
ganhar pontos extra a fim de melhorar a nota da primeira prova. A nota a ser atribu\'{\i}da
\`a primeira prova ser\'a o m\'{\i}nimo entre os valores $n+t$ e 17, onde $n$ \'e a nota
da prova e $t$ \'e a nota do trabalho pr\'atico.

\vspace*{5mm}
\begin{flushleft}\bf\large
Descri\c c\~ao do Problema
\end{flushleft}

Inspirado no algoritmo da Figura 1.5, p\'agina 94 da apostila, escreva um programa
na linguagem de sua prefer\^encia que, recebendo como entrada um AFD $M$ e uma palavra
$w$, determine se $M$ reconhece $w$.

O programa dever\'a ser {\em interativo\/}, com o usu\'ario podendo fornecer um novo
AFD ou uma nova palavra de entrada quando bem entender.

Para simplificar o programa, voc\^e pode impor restri\c c\~oes, como, por e\-xem\-plo,
exigir que os estados sejam n\'umeros a partir de 0, at\'e uma constante definida no
in\'{\i}cio do programa, exigir que cada s\'{\i}mbolo do alfabeto seja constitu\'{\i}do
de apenas um car\'ater, etc.

Dever\~ao ser entregues a listagem do programa (que deve ser auto-do\-cu\-men\-ta\-do) e um
conjunto de instru\c c\~oes de uso. Al\'em disso, dever\'a ser feita uma demonstra\c c\~ao
de uso do programa. Em tal demonstra\c c\~ao, o professor ir\'a testar o funcionamento
do programa usando exemplos de sua pr\'opria escolha.

\vspace*{5mm}
\begin{flushleft}\bf\large
Um Exemplo
\end{flushleft}

Segue um exemplo de intera\c c\~ao com um programa implementado em Prolog. Observe que
voc\^e n\~ao precisa implementar um programa que funcione exatamente desta forma, mas
o grau de intera\c c\~ao deve ser neste n\'{\i}vel.

Ap\'os ativado, o programa \'e acionado come\c cando com \verb+:-+ (coisas da linguagem
Prolog). Vamos supor que o usu\'ario escreve que deseja entrar com um AFD $M$ de 3 estados,
alfabeto $\{0,1\}$, estado inicial 0, e conjunto de estados finais $\{1\}$ assim:

\begin{verbatim}
:- afd(M,3,[0,1],0,[1],[[0,0,0],  /* delta(0,0) = 0, etc... */
                        [0,1,1],
                        [1,0,2],
                        [1,1,1],
                        [2,0,2],
                        [2,1,2]]).
\end{verbatim}

\noindent (N\~ao ligue para a sintaxe. Ela foi escolhida de forma a facilitar o processamento em
Prolog. Fa\c ca uma escolha que lhe d\^e um m\'{\i}nimo de trabalho na sua linguagem.)
O usu\'ario pede para verificar se $M$ aceita a palavra 001:

\begin{verbatim}
:- aceita(M,[0,0,1]).
\end{verbatim}

\noindent O programa responde que {\em sim\/}.
O usu\'ario pede para verificar se $M$ aceita a palavra 01011:

\begin{verbatim}
:- aceita(M,[0,1,0,1,1]).
\end{verbatim}

\noindent O programa responde que {\em n\~ao\/}. E assim por diante.
Suponha que o usu\'ario entra com outro AFD:

\begin{verbatim}
:- afd(N,2,[a,b],0,[0],[[0,a,0],      /* delta(0,a) = 0, etc. */
                        [0,b,1],
                        [1,a,1],
                        [1,b,0]]).
\end{verbatim}

\noindent Agora ele pode consultar por aceita\c c\~ao de palavras pelos  AFD's $M$ e $N$. 


\end{document}
 

