% % 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 % 2000/2001 % \documentclass[12pt]{article} \usepackage{a4wide} \usepackage{graphics} \usepackage{graphicx} \usepackage{color} \usepackage{alltt} \usepackage{portuges} \usepackage[latin1]{inputenc} \usepackage{latexsym} \usepackage[dvips]{epsfig} \usepackage{epic} \usepackage{eepic} \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] \title{\sf Métodos de programação III \\ \begin{tabular}{c} {\small LMCC \& LESI}, {\small Universidade do Minho} \\ {\small Ano lectivo 2000/2001} \\ {\small Trabalho Prático N$º$1} \\ \textbf{\small Conversão de Autómatos Finitos Não-Deterministas em Deterministas} \\ \end{tabular} } \author{\small Grupo: \begin{tabular}[t]{lll} 55436 & LESI & Ana \\ 40000 & MCC & Tó \\ 33333 & MCC & Zé \\ \end{tabular} } \date{} %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle Neste trabalho prático pretende-se que os alunos implementem a conversão de um autómato finito não-determinista (AFND) para um autómato finito determinista (AFD). \bigskip \noindent \begin{tabular}{rl} \hline \\ \textbf{Entrega da Trabalho:} & data limite é \textit{30/11/00} \\ & A entrega é feita por email para \verb#jas@di.uminho.pt# \\ & (uma resposta ao email será enviada a confirmar a entrega) \\ \\ \textbf{Constituição dos Grupos:} & Os grupos terão obrigatoriamente \textbf{3 elementos} \\ \\ \textbf{Linguagem de Prog.:} & Haskell \\ & (embora não aconselhado o trabalho poderá ser feito em C) \\ \\ \hline \end{tabular} \bigskip O enúnciado do trabalho prático está escrito em \textbf{literate Haskell}. Isto é, pode ser interpretado como um documento \LaTeX\ ou como um puro programa na linguagem Haskell. Resolva este trabalho prático neste mesmo ficheiro de modo a implementar o programa e a sua documentação. \section{Algoritmo de Conversão} A ideia geral do método de conversão de um AFND num AFD é a seguinte: a cada estado do AFD corresponde um conjunto de estados do AFND. Isto acontece porque o reconhecimento de uma frase por um AFND pode ser feito utilizando caminhos diferentes (e consequentemente sequências de estados diferentes). Assim, cada estado de um AFD contém a informação (i.é., os estados) que se podem alcançar a partir de um estado do AFND transitando por um dado símbolo do vocabulário. Considerando o autómato finito não-determinista ${\cal A}_{nd} = ({\cal V},{\cal Q},{\cal S}, {\cal Z}, {\cal \delta})$ e o autómato finito determinista ${\cal A}_{d} = ({\cal V'},{\cal Q'},{\cal S'}, {\cal Z'}, {\cal \delta'})$ a conversão de ${\cal A}_{nd}$ em ${\cal A}_{d}$ é feita do seguinte modo: \begin{itemize} \item ${\cal V'}$ = ${\cal V}$ \item ${\cal S'}$ = $\epsilon${\em -fecho} \ $\delta \ \{\cal S\}$ \item $\delta' \ X \ v$ =$\epsilon${\em -fecho}$ \ (\bigcup_{q \in X} \ \delta \ q \ v )$, para todo $v \in {\cal V}$ \item ${\cal Q'}$ define-se recursivamente por: \begin{itemize} \item ${\cal S'\in Q'}$ \item $X \in {\cal Q'} \wedge (\delta'\ X \ v) \neq \emptyset \Rightarrow (\delta'\ X \ v) \in {\cal Q'}$ % \item $X \in {\cal Q'} \wedge ((X,T),q) \in \delta' \Rightarrow q % \in {\cal Q'}$ \end{itemize} \item ${\cal Z'}$ = $\{ X \in {\cal Q'} | X \cap {\cal Z} \neq \emptyset \}$ \end{itemize} Informalmente estas regras dizem o seguinte: o vocabulário do autómato finito determinista ${\cal T'}$ é o mesmo que o do não determinista. O seu estado inicial ${\cal S'}$ é o conjunto formado pelos estados que se alcançam a partir do estado inicial do AFND transitando por $\epsilon$. O conjunto de transições ${\cal \delta'}$ obtém-se do seguinte modo: para cada estado $X$ do AFD e para cada símbolo do vocabulário $v$ obtém-se, caso exista, uma transição para um novo estado. Este novo estado do AFD é obtido através do $\epsilon${\em -fecho} da união dos estados que se alcançam no AFND a partir dos estados que constituem $X$\footnote{Recorde-se que $X$, i.é, um estado de um AFD, é formado por um ou mais estados do AFND.}, transitando por $v$. O conjunto de estados ${\cal Q'}$ do AFD é constituído pelo seu estado inicial e ainda por todos os estados que se alcançam em transições de um estado de ${\cal Q'}$ por um símbolo do vocabulário. O conjunto de estados finais ${\cal Z'}$ é formado por todos estados do AFD que incluem algum estado final do AFND. \medskip Uma técnica bastante mais sistemática para efectuar a conversão entre um AFND e um AFD consiste na utilização de uma {\em tabela} que auxilia o processo de conversão. Esta tabela é constituída por várias colunas. A primeira coluna está associada aos estados do AFD e as restantes colunas estão associadas a cada um dos símbolos do vocabulário. Cada linha da tabela define as transições associadas ao estado do DFA que consta da sua primeira coluna. Esta tabela é preenchida do seguinte modo: a primeira coluna da primeira linha preenche-se com o estado inicial do AFD (calculado através do $\epsilon${\em -fecho} dos estados iniciais do AFND). Cada uma das colunas restantes preenchem-se com $\epsilon${\em -fecho} dos estados que se alcançam partindo do estado inicial e transitando por ramos com o peso do símbolo associado à coluna. Cada um destes conjuntos de símbolos encontrados corresponderá um novo estado do AFD. Para cada novo estado proceder-se-á de igual modo, i.é, acrescentando uma linha na tabela, pondo esse estado na primeira coluna e determinando as suas transições. O processo termina quando os estados encontrados já estiverem todos considerados. \section{Um Exemplo} Consideremos a definição do seguinte autómato finito não-determinista apresentado na ficha teórico-prática n$º$4: ${\cal A}_2 = ({\cal V}_2,{\cal Q}_2,{\cal S}_2, {\cal Z}_2, {\cal \delta}_2)$, com ${\cal V}_2 = \{ 'a', 'b','c' \}$, ${\cal Q}_2 = \{ A,B,C,D\}$, $ {\cal S}_2 = \{A,B\}$, ${\cal Z}_2 = \{ D \}$ e a função de transição é \begin{tabular}[t]{lcl} $\delta_2$ \ \ A \ 'a' & = & \{B\} \\ $\delta_2$ \ \ A \ $\epsilon$ & = & \{A,D\} \\ $\delta_2$ \ \ B \ 'b' & = & \{C\} \\ $\delta_2$ \ \ B \ $\epsilon$ & = & \{D\} \\ $\delta_2$ \ \ C \ $\epsilon$ & = & \{B,D\} \\ $\delta_2$ \ \ D \ $\epsilon$ & = & \{D\} \\ $\delta_2$ \ \ D \ 'c' & = & \{D\} \\ \end{tabular} \medskip Utilizando a técnica definida anteriomente obtemos a seguinte tabela auxialiar de conversão: \medskip \begin{center} \begin{tabular}{|c|c|c|c|} \hline $ _{\cal Q'}{\large \verb@\@} ^{\cal T'}$ & $'a'$ & $'b'$ & $'c'$ \\ \hline ${\cal S'} = \{ABD\}$ & $\epsilon${\em -fecho}$(\{B\})$ & $\epsilon${\em -fecho}$(\{C\})$ & \{\} \\ & $= \{B,D\}$ & $= \{C,B,D\}$ & \\ \hline $\{B,D\}$ & \{\} & $\epsilon${\em -fecho}$(\{C\})$ & $\epsilon${\em -fecho}$(\{D\})$ \\ & & $= \{C,B,D\}$ & $= \{D\}$ \\ \hline $\{CBD\}$ & \{\} & $\epsilon${\em -fecho}$(\{C\})$ & $\epsilon${\em -fecho}$(\{D\})$ \\ & & $= \{C,B,D\}$ & $= \{D\}$ \\ \hline $\{D\}$ & \{\} & \{\} & $\epsilon${\em -fecho}$(\{D\})$ \\ & & & $= \{D\}$ \\ \hline \end{tabular} \end{center} \section{A Implementação em Haskell} A implementação em Haskell vai ser feita em duas etapas: \begin{itemize} \item Primeiro, definimos uma função que dado um autómato finito não-determinista constroi a tabela de conversão, tal como explicado anteriormente. \item Depois, definimos uma função que a partir do autómato finito não determinista e da tabela de conversão construída, constroi o autómato finito determinista equivalente. \end{itemize} Antes de implementarmos estas funções vamos definir um novo módulo com nome \texttt{NdfaToDfa} e os módulos que este importa: \texttt{Dfa} e \texttt{Ndfa}, ambos os módulos desenvolvidos nas aulas teórico-práticas. \medskip \begin{code} module NdfaToDfa where import Dfa import Ndfa \end{code} \medskip \subsection{A função \texttt{ndfa2tt}} De seguida necessitamos definir o tipo da tabela auxiliar na conversão dos autómatos. O seu tipo é o seguinte: \medskip \begin{code} TT st = [ ([st] , [[st]]) ] \end{code} \medskip e agora estamos em posição de definir a função \texttt{ndfa2tt} que converte um autómato finito não determinista numa tabela de conversão: \medskip \begin{code} ndfa2tt :: Eq st => Ndfa st Char -> TT st \end{code} \medskip Nesta conversão usamos as seguintes funções auxiliares \medskip \begin{code} \end{code} \subsubsection{Um exemplo da implementação} Consideremos de novo o autómato finito não-determinista da aula-teórico prática n$º$4. Se executarmos o Hugs obtemos: \medskip \begin{verbatim} Ndfa> ndfa2tt ndfa_A_2 [("ABD",["BD","CBD",""]), ("BD",["","CBD","D"]), ("CBD",["","CBD","D"]), ("D",["","","D"])] \end{verbatim} \medskip \subsection{A função \texttt{ndfa2dfa}} Agora estamos em posição de definir a função \texttt{ndfa2dfa} \medskip \begin{code} ndfa2dfa :: Eq st => Ndfa st Char -> Dfa [st] Char ndfa2dfa ndfa@(Ndfa v q s z delta) = (Dfa v' q' s' z' delta') where tt = ndfa2tt ndfa v' = v q' = statesTT tt s' = fst (head tt) z' = finalStatesDfa tt z delta' = tt2tf where tt2tf st sy = lookupTT st sy tt v lookupTT :: (Eq st, Eq sy) => st -> sy -> TT st -> [sy] -> [st] lookupTT st sy [] v = [] lookupTT st sy (q:qs) v | (fst q == st) = (snd q) !! col | otherwise = lookupTT st sy qs v where col = just (elemIndex sy v) just (Just a) = a \end{code} \section{Resultados} \section{Extras ao trabalho prático} \begin{enumerate} \item Geração do autómato finito determinista. Pretende-se desenvolver uma função que gera o código Haskell do AFD num ficheiro de texto (isto é, um programa Haskell). \item Conversão de Expressões Regulares (abstractas) em autómatos finitos deterministas. As expressões regulares são representadas pelo tipo \texttt{RegExp}. Um primeiro catamorfismo traduz um valor deste tipo num autómato finito não-determinista. Posteriormente, a função \texttt{ndfa2tt} converte-o num autómato determinista. \end{enumerate} \end{document}