% 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 % 2003/2004 % \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} \def\Ipe#1{\def\IPEfile{#1}\input{#1}} \def\hask{\textsf{Haskell}} \def\hugs{\textsf{Hugs}} \newenvironment{code} {\vspace{0.3cm} \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}{Exercício}[section] \title{Métodos de Programação III\\ LESI + LMCC (3º ano)} \author{Ficha Teórico-Prática nº 7\\ (Autómatos Não-Deterministas (2))} \date{Ano lectivo 2003/2004} %\date{\today} %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle \noindent Este texto está escrito em \textbf{Literate Haskell}. Isto é, 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 mp303f07.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 mp303f07.lhs}\end{center} Para isso o código \hask\ deve estar delimitado pelos comandos \verb@\@\texttt{begin\{code\}} e \verb@\@\texttt{end\{code\}}.\\\\ Responda às perguntas sobre \hask\ neste próprio ficheiro para assim produzir o programa e a sua documentação. \section{Conversão de Autómatos Finitos Não Deterministas em Deterministas} A ideia geral do método de conversão de um autómato finito não determinista completo num autómato finito determinista completo é 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 -closure} \ $\delta \ {\cal S}$ \item ${\cal Q'}$ define-se recursivamente por: \begin{itemize} \item ${\cal S'\in Q'}$ \item $qs \in {\cal Q'} \Rightarrow (\delta'\ qs \ v) \in {\cal Q'}$, para todo $v \in {\cal V}$ \end{itemize} \item $\delta' \ qs \ v$ = $walk \ \delta \ qs \ \langle v \rangle$ \item ${\cal Z'}$ = $\{ q \in {\cal Q'}\ |\ q \cap {\cal Z} \neq \emptyset \}$ \end{itemize} \noindent em que as funções $\epsilon${\em -closure} e $walk$ foram definidas formalmente na ficha teórico-prática n$º$4. Informalmente estas regras dizem o seguinte: o vocabulário do autómato finito determinista ${\cal V'}$ é o mesmo que o do não determinista. O seu estado inicial ${\cal S'}$ é o conjunto formado pelos estados iniciais do AFND e todos os que se alcançam transitando por $\epsilon$ (i.e. sem consumir nenhum símbolo). 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 $v$. O conjunto de estados finais ${\cal Z'}$ é formado por todos estados do AFD que incluem algum estado final do AFND. \begin{exercicio} Considere o seguinte autómato finito não determinista ${\cal A}_1 = ({\cal V}_1,{\cal Q}_1,{\cal S}_1, {\cal Z}_1, {\cal \delta}_1)$, com ${\cal V}_1 = \{ 'a', 'b'\}$, ${\cal Q}_1 = \{ A,B,C\}$, $ {\cal S}_1 = \{A\}$, ${\cal Z}_1 = \{ D \}$ e a função de transição é \begin{center} \begin{tabular}[t]{lcl} $\delta_1$ \ \ A \ 'a' & = & \{B,C\} \\ $\delta_1$ \ \ A \ $\epsilon$ & = & \{D\} \\ $\delta_1$ \ \ B \ 'a' & = & \{C\} \\ $\delta_1$ \ \ C \ 'b' & = & \{D\} \\ $\delta_1$ \ \ D \ $\epsilon$ & = & \{C\} \\ $\delta_1$ \ \ \_ \ \_ & = & \{\} \\ \end{tabular} \end{center} Calcule um autómato determinista equivalente. \end{exercicio} %-------------------- \subsection{Construção de uma Tabela de Conversão} Uma técnica bastante mais sistemática e estruturada 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 que chamamos \textit{tabela de conversão}, é 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 -closure} dos estados iniciais do AFND). As restantes colunas da primeira linha da tabela preenchem-se com o conjunto de estados que se alcançam caminhando no AFND a partir do conjunto de estados da primeira coluna e consumindo a frase constituída por um caracter: o símbolo do vocabulário 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. Isto é, o processo convergir. \subsection{Um Exemplo} Consideremos de novo o autómato finito não-determinista ${\cal A}_1$ do exercício anterior. Utilizando a técnica definida anteriormente obtemos a seguinte tabela auxiliar de conversão: \medskip \small \begin{center} \begin{tabular}{|c|c|c|} \hline $ _{\cal Q'}{\large \verb@\@} ^{\cal T'}$ & $'a'$ & $'b'$ \\ \hline ${\cal S'} = \epsilon${\em -closure} \ $\delta_1 \ {\cal S}_1$ & $walk \ \delta_1 \ \{A,D,C\} \ ['a']$ & $walk \ \delta_1 \ \{A,D,C\} \ ['b']$ \\ $= \{A,D,C\}$ & $= \{B,C\}$ & $= \{C,D\}$ \\ \hline $\{B,C\}$ & $walk \ \delta_1 \ \{B,C\} \ ['a']$ & $walk \ \delta_1 \ \{B,C\} \ ['b']$ \\ & = \{C\} & $= \{C,D\}$ \\ \hline $\{C,D\}$ & $walk \ \delta_1 \ \{C,D\} \ ['a']$ & $walk \ \delta_1 \ \{C,D\} \ ['b']$ \\ & = \{\} & $= \{C,D\}$ \\ \hline $\{C\}$ & $walk \ \delta_1 \ \{C\} \ ['a']$ & $walk \ \delta_1 \ \{C\} \ ['b']$ \\ & = \{\} & = \{C,D\} \\ \hline $\{\}$ & $\{\}$ & $\{\}$ \\ \hline \end{tabular} \end{center} \normalsize \begin{exercicio} \label{exerc:afnd2afd1} Considere as seguintes linguagens regulares modeladas pelas seguintes expressões regulares: \begin{enumerate} \item ${\cal L} = (a + b)^* abb$ \item \label{exerc:convReais} ${\cal L}_{reais} = ('+' + '-')?\ d^*\ ('.')?\ d^+$ \end{enumerate} Para cada uma destas linguagens apresente um autómato finito não determinista que as definem. Calcule os autómatos deterministas equivalentes (utilize as regras de conversão de autómatos não deterministas em deterministas). \end{exercicio} %-------------------- \section{Conversão de Autómatos Finitos Não-Deterministas em Deterministas em Haskell} Vamos agora construir em Haskell a função de conversão de autómatos não deterministas completos para autómatos deterministas completos. Começamos por definir um novo módulo chamado \texttt{Ndfa2Dfa}: \begin{code} module Ndfa2Dfa where import List import RegExp import Dfa import Ndfa \end{code} Para tornar os tipos, e consequentemente as funções, mais legíveis vamos definir um tipo para os estados do autómato determinista que se obtém após a conversão, (isto é, o tipo \texttt{StDfa} que é uma lista de estados do AFND) e o tipo da tabela de conversão (tipo \texttt{CT}): \begin{code} type StDfa st = [st] type CT st = [( StDfa st, [StDfa st])] \end{code} Para desenvolver a função de conversão vamos necessitar de algumas funções auxiliares. Note que a função \texttt{epsilon\_closure} foi já definida na ficha teórica anterior, portanto a primeira coluna da primeira linha da tabela pode ser calculada facilmente por esta função. Vamos então definir uma função que preenche as restantes colunas da tabela. Assim, definimos a função \texttt{OneRow} que dada a função de transição de estado, o estado do AFD que está na primeira coluna, o alfabeto, calcula (através da função já definida \texttt{ndfawalk}) a lista de estados (do AFD) para cada uma das restantes colunas da tabela: \begin{code} oneRow :: Ord st => (st -> Maybe sy -> [st]) -> StDfa st -> [sy] -> [StDfa st] oneRow _ _ [] = [] oneRow delta st (v:vs) = (sort (ndfawalk delta st [v])) : (oneRow delta st vs) \end{code} \begin{exercicio} \label{exerc:afnd2afd2} Considere de novo o autómato ${\cal A}_1$. Modele este autómato em Haskell e utilize as funções anteriores e a sua execução no sistema Hugs de modo a: \begin{enumerate} \item Calcular a primeira coluna da primeira linha da tabela de conversão, calculando ($\epsilon\textit{-closure} \ \delta_1 \ {\cal S}_1$). \item Calcular o valor das restantes colunas da primeira linha da tabela, usando a função \texttt{oneRow}. \label{exerc:afnd2afd2_2} \end{enumerate} \begin{code} {- f5_ndfa_a1 = f5_delta_a1 f5_delta_a1 f5_delta_a1 f5_delta_a1 f5_delta_a1 f5_delta_a1 -} -- alinea_1 = -- alinea_2 = \end{code} \end{exercicio} %-------------------- Uma linha da tabela introduz (potencialmente) novos estados do autómato finito determinista. Cada um destes estados induz, por sua vez, uma nova linha na tabela. Seguidamente definimos uma função \texttt{consRows} que constrói linhas completas da tabela. Esta função tem como argumentos a função de transição de estados, um conjunto de estados (do AFD) e o alfabeto. A função constrói uma tabela de transição de estados. \begin{code} consRows :: Ord st => (st -> Maybe sy -> [st]) -> [StDfa st] -> [sy] -> CT st consRows delta [] v = [] consRows delta (q:qs) v = nub ((q , oneRow delta q v) : (consRows delta qs v)) \end{code} \begin{exercicio} No exercício \ref{exerc:afnd2afd2}.\ref{exerc:afnd2afd2_2}, introduziram-se dois novos estados no autómato finito determinista. Calcule, com auxilio da função \texttt{consRows}, as novas linhas da tabela de conversão que esses estados induzem. \begin{code} -- alinea_3 = \end{code} \end{exercicio} %-------------------- Até este momento, temos apenas funções que trabalham com linhas da tabela de conversão. Vamos agora definir uma função que dado uma tabela de conversão parcialmente preenchida contrói uma nova tabela de conversão "totalmente" preenchida. Por uma tabela parcialmente preenchida entendemos uma tabela em que existem estados nas colunas do lado direito que ainda não foram considerados, isto é, ainda não deram origem a uma linha. \begin{code} ndfa2CtStep :: Ord st => (st -> Maybe sy -> [st]) -> [sy] -> CT st -> CT st ndfa2CtStep delta v [] = [] ndfa2CtStep delta v ((s,ss):rs) = (s,ss):(consRows delta ss v) `union` (ndfa2CtStep delta v rs) \end{code} \begin{exercicio} \label{exerc:tc1} Considere a primeira linha da tabela de conversão: \begin{verbatim} [("ACD",["BC","CD"])] \end{verbatim} Calcule a tabela de conversão que se obtém com a função \texttt{ndfa2CtStep}. A tabela obtida está totalmente preenchida? \begin{code} -- alinea_4 = \end{code} \end{exercicio} %-------------------- Como a alínea anterior prova a tabela que se obtém está de novo parcialmente preenchida uma vez que os estados que ainda não tinham sido considerados induziram novos estados que não estão a ser considerados nesta. Portanto, precisamos de repetir a construção da tabela até que o processo convirja, isto é, todos os estados estejam considerados. \begin{exercicio} Considere de novo a tabela de construção do autómato deterministas. \begin{enumerate} \item Execute de novo a função \texttt{ndfa2CtStep} em que a tabela de conversão passada como argumento é a tabela construída no exercício \ref{exerc:tc1}. \item Execute de novo a função \texttt{ndfa2CtStep} em que a tabela de conversão passada como argumento é a tabela construída na alínea anterior. \end{enumerate} \begin{code} -- alinea_4b = -- alinea_4c = \end{code} \end{exercicio} %-------------------- Isto é, a função convergiu após $3$ invocações. Em Haskell usamos a função \texttt{limit} para definir o limite de uma função. A função \texttt{ndfa2ct} utiliza a função \texttt{limit} (da função \texttt{ndfa2CtStep}) para calcular a tabela de conversão. Como tabela inicial é passada uma tabela que contém unicamente a sua primeira linha preenchida. \begin{code} ndfa2ct :: Ord st => Ndfa st sy -> CT st ndfa2ct (Ndfa v q s z delta) = limit (ndfa2CtStep delta v) ttFstRow where ttFstRow = consRows delta [epsilon_closure delta s] v \end{code} \begin{exercicio} Considere de novo o autómato ${\cal A}_1$. Utilize a função \texttt{ndfa2ct} para calcular a tabela de conversão. \begin{code} -- alinea_5 = \end{code} \end{exercicio} %-------------------- \begin{exercicio} Considere os autómatos finitos não deterministas definidos no exercício \ref{exerc:afnd2afd1}. Utilize a implementação em Haskell para provar que as tabelas de conversão obtidas estão correctas. \end{exercicio} %-------------------- A construção da tabela de conversão é apenas um passo intermédio no processo de conversão de um AFND em AFD. A seguir apresenta-se a função \texttt{ndfa2dfa} que recebe como argumento um AFND e constrói um AFD. Analise com atenção esta função e o seu tipo. \begin{code} ndfa2dfa :: (Ord st,Eq sy) => Ndfa st sy -> Dfa [st] sy ndfa2dfa ndfa@(Ndfa v q s z delta) = (Dfa v' q' s' z' delta') where tt = ndfa2ct ndfa v' = v q' = map fst tt s' = fst (head tt) z' = finalStatesDfa q' z delta' st sy = lookupCT st sy tt v finalStatesDfa :: Eq st => [StDfa st] -> [st] -> [StDfa st] finalStatesDfa [] z = [] finalStatesDfa (q:qs) z | (q `intersect` z /= []) = q : finalStatesDfa qs z | otherwise = finalStatesDfa qs z lookupCT :: (Eq st, Eq sy) => [st] -> sy -> CT st -> [sy] -> StDfa st lookupCT st sy [] v = [] lookupCT st sy (q:qs) v | (fst q == st) = (snd q) !! col | otherwise = lookupCT st sy qs v where (Just col) = elemIndex sy v \end{code} \begin{exercicio} Considere de novo o exercício~\ref{exerc:afnd2afd1}-\ref{exerc:convReais} que define a linguagem dos números reais. \begin{enumerate} \item Modele a expressão regular, o autómato finito não determinista e o autómato determinista (obtido) em Haskell. \begin{code} \end{code} \item Prove que $"153.148" \in {\cal L}_{reais}$. Utilize o sistema Hugs para comparar a complexidade de cada uma das funções de aceitação implementados nas aulas teórico-práticas, i.e., as funções \texttt{matches'}, \texttt{dfaaccept} e \texttt{ndfaaccept}, para reconhecer essa frase. Qual o número de reduções efectuado pelo interpretador para cada uma das funções reconhecer a frase $"153.148"$? (o número de reduções do Hugs é activado fazendo \texttt{:set +s})\footnote{Obtenha os resultados para cada uma das funções, em diferentes execuções do interpretador.}. Qual o número de reduções efectuado quando uma função é invocada duas vezes consecutivas com os mesmos argumentos? A que se deve essa diferença? \begin{code} \end{code} \end{enumerate} \end{exercicio} %-------------------- \end{document}