\documentclass[11pt,a4paper]{article}
\usepackage[portuguese]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}

\begin{document}

\selectlanguage{portuguese}

\begin{tabular*}{\linewidth}{l@{\extracolsep{\fill}}r}
  Graduação em Ciência da Computação           & DCC/ICEx/UFMG \\
  \textit{Fundamentos da Teoria da Computação} & 1 semestre de 2003\\
  Professor: Newton José Vieira                & \\
  email: \texttt{nvieira@dcc.ufmg.br}          & \\
  \textbf{Primeiro Trabalho Prático}           & Entrega: 29/05/2003
\end{tabular*}

\bigskip

\textbf{Objetivo}: construir autômatos finitos determinísticos (AFD) que
permitem o reconhecimento dos números (escritos em base 10) múltiplos de 3, 6 e
9. Os AFDs vão manipular números escritos de maneira usual, ou seja em base 10. O
alfabeto de entrada é $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$.

Para algumas questões deste trabalho prático, é melhor usar um software do tipo
\texttt{JFLAP}\footnote{Disponível neste endereço:
  \texttt{http://www.cs.duke.edu/$\sim$rodger/tools/tools.html}}, ou outro
software capaz de gerar e manipular AFDs.

As questões são as seguintes: 

\begin{enumerate}
\item Construa um AFD $A_{1}$ que reconheça os múltiplos de 3. Por exemplo,
  $\{3,9,456,1624782\} \subset L\left(A_{1}\right)$. Por convenção, 0 é múltiplo
  de qualquer outro número.
\item Construa um AFD $A_{2}$ que faça o somatório dos dígitos da palavra de
  entrada, de maneira a obter um número entre $0$ e $9$. Por exemplo, se a
  palavra de entrada é $w=15$, o autômato deve parar num estado representativo
  do resultado $6$ porque $1+5=6$. Se $w=7491$, o autômato deve parar num estado
  representativo do resultado $3$, porque $7+4+9+1=21$ e $2+1=3$. Perceba que
  $A_{2}$ aceita qualquer palavra. O importante é o estado atingido com a
  palavra de entrada $w$. Para gerar este autômato, é preferível usar um
  software.
\item Verifique o bom funcionamento do seu autômato $A_{2}$ com uma dezena de
  entradas representativas.
\item Transforme $A_{2}$ em $A_{3}$ de maneira que $L\left(A_{3}\right)$ seja o
  conjunto dos múltiplos de $3$.
\item Transforme $A_{2}$ em $A_{4}$ de maneira que $L\left(A_{4}\right)$ seja o
  conjunto dos múltiplos de $9$.
\item Verifique o bom funcionamento dos seus autômatos $A_{3}$ e $A_{4}$ com
  algumas entradas.
\item Com o software escolhido, minimize os AFDs $A_{3}$ e $A_{4}$.
\item Construa um autômato $A_{5}$ reconhecendo os números pares.
\item Construa um autômato $A_{6}$ reconhecendo os números múltiplos de 6.
\end{enumerate}

O trabalho a ser entregue é a resposta a estas questões. Para os AFDs gerados
com um software, inclua um \textit{screenshot} do autômato. Se o software JFLAP
for usado, salvar os AFDs em arquivos com os nomes \texttt{a1.nfa},
\texttt{a2.nfa}, \ldots; e os mande para o endereço seguinte:
\texttt{ghuiban@dcc.ufmg.br}.

Todos os comentários relacionados com este trabalho prático (dificuldade,
quantidade de trabalho, etc.) são bem-vindos.
\end{document}

% LocalWords:  AFDs JFLAP rodger screenshot nfa
