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

\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^{\uvec{o}}$ semestre de 2003\\
  Professor: Newton José Vieira                & \\
  email: \texttt{nvieira@dcc.ufmg.br}          & \\
  \textbf{Segundo Trabalho Prático}           & Entrega: 02/07/2003
\end{tabular*}

\bigskip

\noindent {\bf Observações:}
\begin{itemize}
\item O trabalho deverá ser feito por 1 ou 2 alunos. Em hipótese alguma serão aceitos grupos com mais de 2 alunos.
\item Deverá ser entregue um relatório completo em papel.
\item O trabalho deverá ser entregue todo de uma vez. Ou seja, após a entrega, não será aceita complementação {\bf em hipótese alguma}.
\item Se o trabalho for entregue com $n$ dias de atraso, {\bf qualquer que seja o motivo}, serão descontados $2^n$ pontos.
\end{itemize}

\section{Busca em texto}

Os autômatos finitos podem ser bastante úteis para se fazer busca em texto. Na primeira parte deste trabalho prático, nós vamos ver isso. Responda, no papel, às perguntas:

\begin{enumerate}

\item Como usar um autômato para fazer buscas num texto (determinar se um texto contém uma palavra ou um padrão dados)? Descreva como funcionaria um algoritmo baseado num autômato para fazer buscas em texto. Quais são os vantagens de usar algoritmos baseados em autômatos?

\item Obtenha um autômato não determinístico baseado no alfabeto $\Sigma = \left\{a,b,c,\ldots,y,z\right\}$ que reconheça as palavras que contêm a subpalavra \texttt{ftc}. Obtenha um autômato determinístico equivalente. Nota: se for mais conveniente, vocês podem definir notações que dizem, por exemplo, ``qualquer símbolo do alfabeto, exceto $f$''.

\item Obtenha um autômato que reconheça as palavras da seguinte linguagem:
  \[L = \left\{w \in \Sigma^{*} \,\,|\,\, |w| \geqslant 4 \text{ e $w$ termina com ``ftc''}\right\}\mbox{.}\]

\item Como construir um autômato que reconhece uma palavra dada, autorizando a substituição de uma (e uma só) letra? Por exemplo, um tal autômato, reconhecendo as palavras que contêm o padrão \texttt{lingua}, reconhece também as palavras que contêm os padrões \texttt{lingue}, \texttt{pingua} ou \texttt{longua}. Construa um tal autômato (que reconheça o padrão \texttt{lingua}, autorizando uma substituição).

\item Como construir um autômato que reconhece uma palavra dada, autorizando uma remoção? Por exemplo, o autômato que reconhece o padrão \texttt{lingua} aceita também as palavras que contêm \texttt{ingua}, \texttt{linua} ou \texttt{lingu}. Construa um tal autômato.

\item Como construir um autômato que reconhece uma palavra dada, autorizando uma inserção? Por exemplo, o autômato que reconhece o padrão \texttt{lingua} aceita também as palavras que contêm \texttt{alingua}, \texttt{lingual} ou \texttt{linglua}. Construa um tal autômato.

\item Construa um autômato que aceite as palavras que contêm \texttt{lingua}, permitindo um erro (substituição, remoção ou inserção).

\item Construa, da mesma forma, um autômato no alfabeto $\Sigma'= \left\{a,b,c\right\}$ que reconheça a palavra \texttt{abc}, permitindo um erro. Obtenha um autômato determinístico equivalente.
\end{enumerate}

Informações úteis sobre este trabalho podem ser encontradas nas notas de aula de Projeto e Análise de Algoritmos do Professor Nivio Ziviani~\cite{Niv03}.

\section{Implementação}

Faça a implementação, numa linguagem de programação qualquer\footnote{O programa deve ser compilável em ambiente Sun ou Linux.}, de um programa que transforma uma expressão regular num AFD. O programa deve ser interativo e o usuário deve ser capaz de entrar com qualquer expressão regular (na forma padrão). O programa deve produzir um AFD na forma $A = \left(E,\Sigma,\delta,i,F\right)$ (não precisa desenhar o AFD). Para simplificar, vocês podem se restringir ao alfabeto $\Sigma=\left\{a,b,c,d\right\}$, e considerar que a expressão regular está sintaticamente correta.

Algoritmos para fazer esta transformação podem ser deduzidos das provas da equivalências entre linguagens reconhecidos por AFDs e por ERs (ver a apostila ou os vários livros sobre o assunto. A bibliografia do plano do curso contém métodos de transformação). Mais detalhes de implementação podem ser encontrados em alguns artigos. Ver~\cite{BS86}, por exemplo.

\section{A ser entregues}

Vocês devem entregar, no papel, as respostas às perguntas da primeira parte. Vocês também devem entregar uma listagem, bem comentada, do programa implementado na segunda parte do trabalho prático, acompanhada de comentários sobre o funcionamento do programa, as dificuldades encontradas, etc. O relatório deve ser entregue no papel (e não de forma eletrônica). Além disso, vocês têm que mandar compactado (zip, tar, tgz, etc) os arquivos fontes do programa, com um \texttt{Makefile}, para o endereço seguinte: \texttt{ghuiban@dcc.ufmg.br}. Os arquivos fontes devem ficar num diretório que tem por nome o(s) login(s) da(s) pessoa(s). Por exemplo, no caso do monitor, os arquivos deveriam ficar num diretório \texttt{ghuiban/}.

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

\bibliography{tp2}
\bibliographystyle{plain}

\end{document}
% LocalWords:  ftc Sun Makefile lingua lingue pingua longua ingua contêm
% LocalWords:  linua lingu alingua linglua abc Nivio Ziviani AFDs
% LocalWords:  ERs zip gzip tar

