\documentclass[12pt, a4paper]{report}
\usepackage[brazil]{babel} % Escrevendo em português 
\usepackage[latin1]{inputenc}
\usepackage{fullpage}

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent Monitor: Leonardo Barbosa e Oliveira \\
\noindent {\bf Trabalho Extra} 


\vspace{1cm}

{\bf Instruções:}

\begin{itemize}
\item O trabalho é individual.

\item Todos os autômatos devem ser gerados
utilizando a ferramenta {\em JFLAP} e possuir um número mínimo de estados.

\item O trabalho deverá ser entregue completo em papel contendo {\it
screenshots} dos autômatos gerados através da ferramenta {\em JFLAP}.

\item A data de entrega é 13/11/2003 e, em hipótese alguma, serão aceitos trabalhos após as 16:30h deste dia. 
\end{itemize}

\vspace{1cm}
\begin{enumerate}

%http://www-db.stanford.edu/~ullman/ialc/win00/hw3.html 1)
%\item Let us consider all possible DFA's with three states; call them p, q, and
%r.  State r is accepting, and the other two are not. We are not going to
%specify a start state. The input symbols are {\tt 0} and {\tt 1}, only. There
%are {\tt 729} different transition functions that this DFA could have, since
%each of the three states can have a transition to any of the three states on
%each of two input symbols. We thus have six choices, each from three objects
%(states), for a total of $3^6 = 729$ transition functions. Some of these
%transition functions cause states p and q to be equivalent. In how many of
%these 729 automata are p and q equivalent? Explain your reasoning. 

%We need to look at which assignment for the transitions from p and q on
%inputs {\tt 0} and {\tt 1} don't allow us to distinguish p from q. Consider the  9
%possible assignments of transitions from p and q on input {\tt 0} ( 3 possible
%states from p x  3 from q =  9). If both states go to r on input {\tt 0}, we cannot
%distinguish them. If they both go to p and / or q, we cannot distinguish
%them. Thus, {\tt 5} of the {\tt 9} assignments do not allow us to distinguish p and q on
%input {\tt 0}. Similar analysis gives the same result for input {\tt 1}. 
%So any combination of the {\tt 5} of {\tt 9} assignments on inputs {\tt 0} and {\tt 1} do not allow
%us to distinguish them, which is {\tt 25} out of the {\tt 81} possible assignments. We
%can combine these with any of the {\tt 9} assignments of transitions from r on
%input {\tt 0} or {\tt 1}, so there are {\tt 225} assignments in which p and q are equivalent. 
%


% http://www-db.stanford.edu/~ullman/ialc/win00/hw1.html  2)
%\item Design a deterministic finite automaton to accept the set of binary strings
%that, when interpreted as an integer, is divisible by  5. Note that the most
%significant digit is the first to be read. Give the five-tuple notation for
%your automaton, with the transition function expressed as a table. Then, draw
%the transition diagram for your FA. Hint: Think of each state as representing
%a particular remainder when the number seen so far is divided by  5. To
%simplify, you may make the reasonable assumption that the empty string
%represents integer {\tt 0}, and thus is one of the accepted strings. 

\item Projete um AFD que aceite um conjunto de palavras binárias que, quando
interpretadas como inteiros, sejam divisíveis por 5. Note que o d\'{\i}gito mais
significativo deve ser o primeiro a ser lido. Para simplificar, você pode supor
que a palavra vazia representa um inteiro divisível por {\tt 0}.

%Dê a notação 5-tupla para seu autômato,
%com a função de transição expressada como uma tabela. Em seguida
%This is the {\tt 5}-tuple definition for one such automaton, as well as the
%transition table; others are possible. Note the problem specifically asked
%for the {\tt 5}-tuple notation of your automaton.
%M = ({q0, q1, q2, q3, q4}, {{\tt 0}, {\tt 1}}, delta, q0, {q0})
%
%
%The transition function delta is described below:
%
%
%State On {\tt 0} On {\tt 1} 
%q0 q0 q1 
%q1 q2 q3 
%q2 q4 q0 
%q3 q1 q2 
%q4 q3 q4 


\item Projete um AFN que aceite o conjunto de palavras sobre \{{\tt 0}, {\tt 1}\} que:

\begin{itemize}
\item terminam com {\tt 010} e contêm {\tt 011}, ou
\item terminam com {\tt 101} e contêm {\tt 100}.
\end{itemize}

% http://www-db.stanford.edu/~ullman/ialc/win00/hw1.html 4)
%\item Design an NFA to accept the set of strings of 0's and 1's that either: 

%\begin{itemize}
%\item End in {\tt 010} and have {\tt 011} somewhere preceding, or 
%\item End in {\tt 101} and have {\tt 100} somewhere preceding. 
%\end{itemize}
%
%In order to make sure that you use nondeterminism, your NFA should have no
%more than 13 states and  15 arcs. You may represent your NFA by a transition
%diagram. 




%The solution to this problem is easiest shown graphically, but I will show it
%here as a transition diagram. There are simpler automata, but I will present
%the most straightforward one (which, incidentally, has 13 states and 15
%arcs): 
%M = ({q_k|1 <= k <= 13}, {0,1}, delta, q0, {q12, q13}) 
%
%delta = 
%
%State On 0 On 1 
%q1 {q1,q2} {q1,q3} 
%q2 {} {q4} 
%q3 {q5} {} 
%q4 {} {q6} 
%q5 {q7} {} 
%q6 {q6,q8} {q6} 
%q7 {q7} {q7,q9} 
%q8 {} {q10} 
%q9 {q11} {} 
%q10 {q12} {} 
%q11 {} {q13} 
%q12 {} {} 
%q13 {} {} 



% http://www-db.stanford.edu/~ullman/ialc/win00/midterm.ps 1)

%() primeira questao da prova 1


%\item Destre as várias utilidade de autômatos finitos está sua utilização
%para buscas de padrões em textos. Quais são as vantagens do uso de algoritmos
%baseados em autômatos? Cite um exemplo destes algoritmos.

\item Como construir um autômato que reconhece uma palavra dada, autorizando
uma remoção? Por exemplo, o autômato que reconhece a palavra {\bf turma}, reconhece
também as palavras {\bf urma}, {\bf tuma} ou {\bf turm}. Construa tal
autômato.

\item Como construir um autômato que reconhece uma palavra dada, autorizando
duas inserç\~oes? Por exemplo, o autômato que reconhece a palavra {\bf turma},
reconhece também as palavras {\bf eturma},  {\bf turmas} ou {\bf turrma}.
Construa tal autômato.

\item Como construir um autômato que reconhece uma palavra dada, autorizando
uma (e apenas uma) substituição? Por exemplo, o autômato que reconhece a
palavra {\bf turma}, reconhece também as palavras {\bf uurma},  {\bf turmi} ou {\bf
tusma}.  Construa tal autômato.

\item Construa um autômato que aceite as palavras que contêm {\bf turma}
permitindo 2 erros (qualquer 2 combinações de substituição, remoção, ou inserção).

\end{enumerate}

\end{document}

