% % Este ficheiro contem um texto em Literate Haskell % Partes do ficheiro são texto em LaTeX e outras em Haskell % % Métodos de Programação III % Universidade do Minho % 2002/2003 % \documentclass[12pt]{article} \usepackage[portuges]{babel} \usepackage[latin1]{inputenc} \usepackage{a4wide} \usepackage{graphics} \usepackage{graphicx} \usepackage{color} \usepackage{alltt} \usepackage{latexsym} \usepackage[dvips]{epsfig} %\usepackage{epic} %\usepackage{eepic} \setlength{\oddsidemargin}{-1cm} \setlength{\textwidth}{18cm} \setlength{\headsep}{-1cm} \setlength{\textheight}{23cm} %formatacao dos paragrafos (nao-indenta; deixa um pequeno espaco) \parindent=0pt \parskip=2pt \def\Ipe#1{\def\IPEfile{#1}\input{#1}} \newenvironment{code} {\textbf{Código Haskell} \hspace{1cm} \hrulefill \\ \smallskip \begin{center} \begin{minipage}{.80\textwidth} \begin{alltt}\small} {\end{alltt} \end{minipage} \end{center} \hrule\smallskip } \newtheorem{exercicio}{}[section] \def\hask{\textsf{Haskell}} \def\hugs{\textsf{Hugs}} \def\xml{\textsf{XML}} \def\lex{\textsf{Lex}} \def\GV{\textsf{GraphViz}} \title{Métodos de Programação III\\ LESI + LMCC (3º ano)} \author{Trabalho Prático nº 2\\ (\textbf{\small Representação Gráfica de Autómatos Finitos e Minimização do Número de Estados})} \date{Ano lectivo 2002/2003\\ Grupo:\\ \begin{tabular}[t]{lll} nnnnn & Lxxx & 1.nome ult.nome \\ nnnnn & Lxxx & 1.nome ult.nome\\ nnnnn & Lxxx & 1.nome ult.nome\\ \end{tabular} } %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle \begin{center} \begin{tabular}{|c|} \hline \\ O trabalho deve ser realizado em grupo, \\ e deve ser entregue acompanhado deste relatório\\ até 13 de Dezembro de 2002 ao fim da tarde \\ \\ \hline \end{tabular} \end{center} \tableofcontents \section{Introdução} Este texto está escrito em \textbf{Literate Haskell} e pretende ser, além do enunciado do 2º Trabalho Práctico da disciplina de MP3, um esboço (ou esquema geral) do relatório que cada grupo tem de apresentar aquando da discussão em computador do projecto realizado. De acordo com o princípio de \emph{Literate Programming}, o código a desenvolver deve aparecer naturalmente inserido no meio do documento. Assim, o documento presente pode ser interpretado como um documento \LaTeX\ ou como um puro programa na linguagem \hask.\\ O documento é obtido "compilando"\ este ficheiro em \LaTeX: \begin{center}\texttt{latex mp302tp2.lhs}\end{center} O programa \hask\ incluído neste ficheiro é compilado/interpretado directamento pelos compiladores/interpretadores de \hask, executando por exemplo o comando: \begin{center}\texttt{hugs mp302tp2.lhs}\end{center} Para isso o código \hask\ deve estar delimitado pelos comandos \verb@\@\texttt{begin\{code\}} e \verb@\@\texttt{end\{code\}}.\\ A ideia essencial do trabalho em causa é gerar código para uma ferramenta de desenho de grafos, o \GV, de modo a poder-se visualizar directamente autómatos finitos (deternimistas ou não).\\ Dessa forma e recorrendo às funcões de conversão desenvolvidas nas aulas teórico-prácticas, será possível desenhar graficamente a linguagem definida por uma dada expressão regular.\\ Complementarmente, pede-se que desenvolva uma função para minimizar o número de estados de um autómato dado. Na resolução desta proposta de trabalho deve ser reutilizado todo o conjunto de funções criadas ao longo do semestre. \subsection{Objectivos e Organização} Neste trabalho prático pretende-se que os alunos implementem um programa em \hask\ para efectuar as seguintes tarefas: \begin{itemize} \item Representação Gráfica de Autómatos Finitos. \item Representação Gráfica de Expressões Regulares. \item Minimização de Estados de Autómatos Finitos. \end{itemize} % Para isso a folha propõe um enunciado único que tem de ser resolvido por todos os grupos, sugerindo-se em apêndice alguns extras que os grupos poderão, ou não, concretizar. \textbf{Os alunos devem ler este enunciado atentamente e completá-lo de modo a obter o relatório do trabalho prático. Para tal, deverão preencher as secções deixadas em branco, incluir o código desenvolvido, completar os parágrafos que estão identificados com ..., apagar partes do enunciado que não façam sentido como documentação do trabalho, etc.} %--------------------------------------------------------------------- \section{Representação Gráfica de Autómatos Finitos} Os autómatos finitos são compreendidos mais facilmente se forem representados numa notação gráfica. Dado um autómato ${\cal A} = ({\cal V},{\cal Q},{\cal S}, {\cal Z}, {\cal \delta})$ uma representação gráfiva é construída de acordo com as seguintes regras: \begin{itemize} \item ... \end{itemize} Por exemplo, o seguinte autómato definido formalmente a seguir ... \medskip induz de acordo com as regras anteriores o seguinte grafo: \section{Representação Gráfica de Expressões Regulares} ... \section{Minimização de Estados de Autómato Finitos} A minimização do número de estado dos autómatos finitos é uma tarefa muito importante devido aos seguintes aspectos: .... \begin{itemize} \item ... \item ... \end{itemize} \section{A Implementação em Haskell} Para a realização deste trabalho foram executadas das seguintes tarefas: \begin{itemize} \item A primeira tarefa consistiu em completar os módulos \texttt{Dfa} e \texttt{Ndfa} (desenvolvidos nas aulas teórico-práticas). Assim, inclui-se as funções \texttt{show} para os tipos \texttt{Dfa} e \texttt{Ndfa}, de modo aos autómatos finitos serem vizualizados textualmente tal como são escritos. Foi ainda útil definir uma função para gravar os autómatos finitos em ficheiro. O tipo desta função é: \begin{verbatim} faIO :: Show fa => fa -> String -> IO () \end{verbatim} Para tal, os tipos \texttt{Dfa} e \texttt{Ndfa} são instâncias da classe \texttt{Show}. \item A segunda tarefa consistiu em utilizar o sistema \GV\ para a vizualização de grafos. O sistema \GV\ está a ser desenvolvido nos laboratórios da \textit{AT\&T} e é de domínio publico: \begin{verbatim} http://www.research.att.com/sw/tools/graphviz/ \end{verbatim} Assim, depois de fazermos o \textit{download} deste software, estudamos a melhor forma de representar autómatos finitos neste sistema. \smallskip \noindent \textit{Nota}: Este sistema processa grafos representados (em ficheiro) numa notação textual. \item Após compreendermos a notação textual dos grafos do sistema \GV, desenvolvemos uma nova função \texttt{show} que representa os autómatos finitos deterministas nessa notação. Definimos ainda uma função que grava em ficheiro os autómatos. Este ficheiro é depois passado ao \GV\ que o apresenta graficamente em vários formatos (postscript, gif, etc). Repetimos esta tarefa para os autómatos finitos não deterministas. Nestes autómatos tivemos de ter em atenção a representação das transições espontâneas (i.e., transições-$\epsilon$). A forma como tratamos estas transições é descrita na secção \ref{sec:ndfa2graph}. \item A terceira tarefa consistiu na representação gráfica de expressões regulares. Mais concretamente, vizualizamos expressões regulares como o autómatos finitos deterministas (equivalentes, i.e., que definem a mesma linguagem). \item A última tarefa consistiu na construção de uma função que efectua a minimização de estados de um autómato finito deterministas. Após termos construído esta função, re-escrevemos a função que representa expressões regulares como autómatos finitos deterministas de modo a utilizar o autómato de estados minimos. \end{itemize} As funções construídas foram incluídas num novo módulo chamado \texttt{DrawFa} que importa os módulos: \texttt{RegExp}, \texttt{Dfa}, \texttt{Ndfa}, \texttt{RegExp2Ndfa}, \texttt{Ndfa2Dfa}, todos eles já desenvolvidos nas aulas teórico-práticas. \begin{code} -- -- Módulo de Minimização de Estados e Representação Gráfica de -- Autómatos Finitos em Haskell -- -- Métodos de Programação III -- Universidade do Minho -- 2001/2002 -- module DrawFa where import RegExp import Dfa import Ndfa import RegExp2Ndfa import Ndfa2Dfa \end{code} \medskip \subsection{A função \texttt{dfa2graph}} \medskip \begin{code} -- dfa2graph :: (Show st, Show sy) => Dfa st sy -> [Char] -> [Char] \end{code} \medskip \subsection{A função \texttt{ndfa2graph}} \label{sec:ndfa2graph} \medskip \begin{code} -- ndfa2graph :: \end{code} \medskip \subsection{A função \texttt{re2graph}} \medskip \begin{code} -- re2DiGraph :: RegExp -> [Char] -> [Char] \end{code} \medskip \subsection{A função \texttt{beautifyDfa}} A função de conversão de um autómato não determinista em determinista constrói um autómato determinista em que os identificadores dos estado são listas. Dependendo da complexidade do autómato, estas listas poderão ter comprimentos razoáveis. Este facto origina que as representações gráficas fiquem pouco claras uma vez que os nomes dos estados ficam enormes. Assim, construímos uma função \texttt{beautifyDfa} que "substitui" esses identificadores de estados por um número apenas. O tipo e a definição desta função apresenta-se a seguir: \medskip \begin{code} -- beautifyDfa :: Eq st => Dfa st sy -> Dfa Int sy \end{code} \medskip tendo esta função definida, podemos então re-escrever a função \texttt{dfa2graph} de modo a utilizar esta representação: \medskip \begin{code} -- dfa2graph' = dfa2graph . beautifyDfa \end{code} \medskip \subsection{A função \texttt{minimizeDfa}} A função de minimização dos estados de um autómato finito determinista completo baseia-se no seguinte algoritmo (apresentado nas aulas teóricas): \begin{enumerate} \item Primeiro, ... \item Segundo, ... \item Terceiro, ... \item Finalmente, ... \end{enumerate} Em Haskell esta função é definida muito simplesmente do seguinte modo: \medskip \begin{code} -- minimizeDfa :: (Eq sy, Ord st) => Dfa st sy -> Dfa [[st]] sy \end{code} \medskip \section{Execução do Programa Desenvolvido} Para ilustrar o bom funcionamento do nosso programa vamos apresentar nesta secção alguns exemplos obtidos com a sua execução.\\ Considere-se a seguinte linguagem regular definida pela expressão regular: \[ er = \] \medskip utilizando a função \texttt{regExp2Ndfa} obtém-se o seguinte autómato finito não determinista: \begin{verbatim} ... \end{verbatim} E utilizando a função de conversão para deterministas obtém-se \begin{verbatim} ... \end{verbatim} Agora minimizando os estados com a função \texttt{minimizeDfa} obtém-se \begin{verbatim} ... \end{verbatim} E podemos agora utilizar as funções de aceitação \texttt{matches}, \texttt{ndfaaccept} e \texttt{dfaaccept} para aceitar a frase ... \begin{verbatim} \end{verbatim} \subsection{Representação Gráfica dos Autómatos} Nesta secção incluimos alguns grafos produzidos pelo sistema \GV\ a partir de autómatos produzidos pelas funções \texttt{dfa2graph} e \texttt{dfa2graph}. \section{Conclusão} ...sintese do conteúdo do relatório...\\ ...estado final do trabalho: requisitos atingidos; requisitos não atingidos; extras...\\ ...trabalho futuro.... \appendix \section{Extras ao trabalho prático} Como trabalho complementar ao conjunto de funções que foram já desenvolvidas, construímos ainda funções extra para realizar as seguintes tarefas\footnote{Os alunos devem apagar deste relatório os extra que não realizaram.}: \begin{enumerate} \item Melhoramos a representação gráfica dos autómatos finitos através da seguinte estratégia: quando do mesmo estado se transita para um outro estado por mais que um símbolo, em vez de se adicionar ao grafo uma seta por cada uma dessas transições, inclui-se apenas uman transição em que a estiqueta são os vários símbolos separados por vírgula. Esta optimização tem sido utilizada inúmeras vezes quando se desenham os autómatos à mão. \item Desenvolvemos uma função que prova que duas expressões regulares são equivalentes ou não. A prova da equivalência de expressões regulares foi feita na aula teórico-prática n$º$2 utilizando para tal a álgebra de expreessões regulares. A função que desenvolvemos efectua a prova através da comparação dos autómatos finitos deterministas minimos que são gerados a partir de cada uma das expressões regulares. Se estes autómatos forem iguais, as expressões regulares são equivalentes, caso contrário as expressões regulares não são equivalentes. \item Analisamos da complexidade dos vários reconhecedores de linguagens regulares. Isto é a complexidade dos vários reconhecedores de linguagens regulares baseados em expressões regulares, autómatos finitos deterministas e não deterministas e autómatos com um número minimo de estados. Para tal consideramos uma dada linguagem e uma frase dessa mesma linguagem, modelamos essa linguagem nos vários modelos apresentados e utilizamos o número de reduções e células usadas pelo interpretador \texttt{Hugs} na aceitação da frase. Obviamente, incluimos neste relatório uma análise e um comentário aos resultados obtidos pelo \texttt{Hugs}. \item Implementamos o algoritmo "\textit{standard}" de minimização de estados de um autómato finito determinista. \item Por último, incluimos ainda a resolução de todas as fichas teórico-práticas que abordam a matéria envolvida neste trabaçho prático. \end{enumerate} \subsection{Desenho dos Autómatos} \subsection{Função de equivalência de Expressões Regulares} \subsection{Desempenho dos Vários Reconhecedores de Linguagens Regulares} \subsection{Função Standard de Minimização de Estados} \end{document}