% 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}

\parindent=0pt
\parskip=3pt

\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º 8\\ (Autómatos Não-Deterministas (3))}
\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 mp303f08.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 mp303f08.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 Expressões Regulares em Autómatos Finitos Não Deterministas}
Nesta ficha vamos definir formalmente o processo de conversão de uma
expressão regular $e$ num autómato finito não determinista $\bf {\cal
A}$ equivalente, i.e., ${\cal L}(e) = {\cal L}({\cal A})$.

Antes de definirmos o processo de conversão formalmente, vamos definir
o módulo \texttt{RegExp2Ndfa} onde vamos expressar a conversão em
Haskell.

\begin{code}
--
-- Módulo de Conversão de Expressões Regulares em 
--                 Autómatos Finitos Não-Deterministas              
--
-- Métodos de Programação III
-- Universidade do Minho
-- 2001/2002
--
module RegExp2Ndfa where
import List
import RegExp
import Dfa
import Ndfa
import Ndfa2Dfa
\end{code}

Em Haskell pretendemos construir uma função que dada uma expressão
regular constrói um autómato finito não determinista. Assumindo que
utilizamos números inteiros para identificar os estados dos autómatos, então
esta função tem tipo:

\begin{code}
regExp2Ndfa :: RegExp -> Ndfa Int Char
\end{code}

Na construção de um autómato não determinista (a partir de uma
expressão regular) vamos ter de introduzir estados. Logo, necessitamos
de usar identificadores únicos para esses estados.  Assim, a função
\texttt{regExp2Ndfa} utiliza uma função auxiliar em que um parâmetro
de acumulação para indicar o número inteiro disponível para ser
utilizado quando um novo estado tem de ser intoduzido no autómato.
Iniciamos este argumento com o valor $1$.

\begin{code}
regExp2Ndfa er = fst (regExp2Ndfa' er 1)
\end{code}

A conversão de expressões regulares em autómatos deterministas faz-se
indutivamente sobre a estrutura da dada expressão regular $\bf e$ a
converter. As regras de conversão apresentam-se de seguida (quer na
sua representação gráfica quer na sua definição na linguagem Haskell):

\begin{minipage}[t]{5cm}
\textbf{1. $\bf e = \epsilon$  converte em}
\end{minipage}
\begin{figure}[htb!]
\begin{center}
%\Ipe{NdfaREepsilon.ipe}
\end{center} 
\end{figure}

Em Haskell introduzimos uma definição alternativa para a função
\texttt{regExp2Ndfa'} que dada uma expressão regular (que modela em
Haskell a expressão regular $\bf \epsilon$) e o número inteiro (que
indica o número que pode ser usado para identificar um novo
estado). Esta função devolve um autómato não determinista com um único
estado $n$ que é simultaneamente inicial e final. A função delta não
define transições para nenhum estado. Como este autómato introduz o
estado $n$, a função devolve como possível número para um novo estado
$n+1$.

\begin{code}
regExp2Ndfa' (Epsilon) n = ( Ndfa [] [sa] [sa] [sa] delta , n+1 )
  where sa = n 
        delta _ _ = []
\end{code}

\begin{minipage}[htb!]{5cm}
\textbf{2. $\bf e = a$  converte em}
\end{minipage}
\begin{figure}[htb!]
\begin{center}
%\Ipe{NdfaRElit.ipe}
\end{center} 
\end{figure}

Em Haskell introduzimos uma definição alternativa para a função
\texttt{regExp2Ndfa'} que dada uma expressão regular (que modela em
Haskell a expressão regular $\bf a$) e o número inteiro (que indica o
número que pode ser usado para identificar um novo estado). Esta
função devolve um autómato não determinista em que o único símbolo do
alfabeto é $a$ e que tem dois estados: um inicial e o outro final. A
função de transição de estados define uma transição do estado inicial
para o final pelo símbolo $\bf a$.  Esta função introduz dois novos
estados $n$ e $n+1$, por isso devolve $n+2$ como possível
identificador para um novo estado.

\begin{code}
regExp2Ndfa' (Literal l) n = ( Ndfa [l] [sa,za] [sa] [za] delta , n+2)
  where sa = n 
        za = n+1
        delta q (Just a) | q == sa && l == a = [za] 
        delta _ _ = []
\end{code}

\begin{minipage}[t]{5cm}
\textbf{3. $\bf e = pq$  converte em}
\end{minipage}
\begin{figure}[htb!]
\begin{center}
%\Ipe{NdfaREthen.ipe}
\end{center} 
\end{figure}

Neste caso a função \texttt{regExp2Ndfa'} define-se através de duas
invocações recursiva para converter as sub-expressões regulares $p$ e
$q$. Tendo os autómatos induzidos por $p$ e $q$ então o autómato
pretendido define-se facilmente em Haskell da seguinte forma:

\begin{code}
regExp2Ndfa' (Then p q) n = ( Ndfa v' q' s' z' delta' , nq)
  where (Ndfa vp qp sp zp dp , np) = regExp2Ndfa' p n
        (Ndfa vq qq sq zq dq , nq) = regExp2Ndfa' q np
        v' = vp `union` vq
        q' = qp `union` qq
        s' = sp
        z' = zq
        delta' q | q `elem` qp = if q `elem` zp then dp' q
                                                else dp  q 
                 | otherwise   = dq q
         where dp' q Nothing = (dp q Nothing) `union` sq
               dp' q (Just a) = dp q (Just a) 
\end{code}

\begin{minipage}[htb!]{5cm}
\textbf{4. $\bf e = p + q$  converte em}
\end{minipage}
\begin{figure}[htb!]
\begin{center}
%\Ipe{NdfaREor.ipe}
\end{center} 
\end{figure}

Neste caso a função \texttt{regExp2Ndfa'} define-se também através de
duas invocações recursiva para converter as sub-expressões regulares
$p$ e $q$. Tendo os autómatos induzidos por $p$ e $q$ então o autómato
pretendido define-se facilmente em Haskell da seguinte forma:

\begin{code}
regExp2Ndfa' (Or p q) n = ( Ndfa v' q' s' z' delta' , nq+1 )
  where (Ndfa vp qp sp zp dp , np) = regExp2Ndfa' p (n + 1)
        (Ndfa vq qq sq zq dq , nq) = regExp2Ndfa' q np
        v' = vp `union` vq 
        s' = [n]
        z' = [nq]
        q' = s' `union` qp `union` qq `union` z'
        delta' q | q `elem` s' = dd q
                 | q `elem` zp = ddp' q
                 | q `elem` zq = ddq' q
                 | q `elem` qp = dp q
                 | q `elem` qq = dq q  
                 | otherwise   = dd'' q
         where dd q  Nothing = sp `union` sq
               dd _ _        = [] 

               ddp' q Nothing = z' `union` (dp q Nothing)
               ddp' _ _       = []

               ddq' q Nothing = z' `union` (dq q Nothing)
               ddq' _ _       = []

               dd'' _ _ = []
\end{code}

\begin{minipage}[t]{5cm}
\textbf{5. $\bf e = p^*$  converte em}
\end{minipage}
\begin{figure}[htb!]
\begin{center}
%\Ipe{NdfaREstar.ipe}
\end{center} 
\end{figure}

Em Haskell escrevemos a seguinte definição alternativa da função
\texttt{regExp2Ndfa'}:

\begin{code}
regExp2Ndfa' (Star p) n = ( Ndfa v' q' s' z' delta' , np+1 )
  where (Ndfa vp qp sp zp dp , np) = regExp2Ndfa' p (n + 1)
        v' = vp 
        s' = [n]
        z' = [np]
        q' = s'  `union` qp `union` z'
        delta' q | q `elem` s' = dd q
                 | q `elem` zp = dd' q
                 | otherwise   = dp q
          where dd q Nothing = sp `union` z'
                dd _ _ = []
                dd' q Nothing = sp `union` z'
                dd' _ _ = []
\end{code}

\begin{exercicio} \label{exerc:afnd2adf1} 
Considere a linguagem regular ${\cal L}$ modelada pelas seguinte
expressão regular $p$:
\[
p = ('+'\ +\ '-'\ +\ \epsilon)\ d\ d* 
\]
e responda às seguintes perguntas:

\begin{enumerate} 

\item Cálcule o autómato finito não-determinista ${\cal A}_{nd}$ tal que
${\cal L}(p) = {\cal L}({\cal A}_{nd})$.

\item Cálcule o autómato finito determinista ${\cal A}_{d}$ tal que
${\cal L}({\cal A}_{d}) = {\cal L}({\cal A}_{nd})$. Diga informalmente
se o autómato obtido tem um número minimo de estados.

\item Modele a expressão regular $p$ em Haskell e utilize as funções
(em Haskell) de aceitação, para cada um dos modelos estudados (i.e.,
expressões regulares e autómatos finitos deterministas e não
deterministas), de modo a provar que $"+153" \in {\cal L}$.

\end{enumerate}

\begin{code}
-- p = 
-- alinea_3_1 = matches p "+153"
-- alinea_3_2 =
-- alinea_3_3 =
\end{code}

\end{exercicio}
%--------------------

\begin{exercicio} \label{exerc:afnd2adf2}
Considere de novo a linguagem ${\cal L}$ do exercício
\ref{exerc:afnd2adf1}. Responda às seguintes perguntas:

\begin{enumerate}

\item Defina (graficamente) o autómato finito não determinista que se
obtém invertendo o autómato determinista ${\cal A}_{d}$. 

Por inversão de um autómato determinista consideramos o
autómato não determinista que se obtém do seguinte modo:

\begin{itemize}
\item invertendo o sentido das transições de estados do AFD

\item considerando como conjunto de estados iniciais o
conjunto de estados finais do AFD.

\item considerando como conjunto de estados finais o conjunto singular
contendo o estado inicial do AFD.
\end{itemize}

\item Converta num autómato determinista o autómato obtido na alínea
anterior.

\item Inverta de novo o autómato determinista obtido na alínea anterior

\item \label{exerc:afnd2adf2_min} Volte a converter em determinista o
autómato obtido.

\item Considere o autómato determinista obtido na alínea anterior e o
autómato ${\cal A}_{d}$ (do exercício \ref{exerc:afnd2adf1}). Diga,
informalmente, se estes autómatos definem a mesma linguagem.

\end{enumerate}
\end{exercicio}
%--------------------

\begin{exercicio} \label{exerc:afnd2adf3}
Modele os autómatos ${\cal A}_{nd}$ e ${\cal A}_{d}$ (do exercício
\ref{exerc:afnd2adf1}) e o autómato construído no exercício
\ref{exerc:afnd2adf2}-\ref{exerc:afnd2adf2_min} em Haskell.  Utilize o
sistema Hugs para comparar a complexidade de cada uma das funções de
aceitação i.e., as funções \texttt{matches}, \texttt{dfaaccept} e
\texttt{ndfaaccept}, para aceitar a frase \("+153"\). Comente os
resultados obtidos.

\begin{code}
-- f5_afnd_a1 = 
-- f5_afd_a1  = 
-- f5_afd_ma1 =
\end{code}

\end{exercicio}
%--------------------

\begin{exercicio} 
Responda às perguntas dos exercícios \ref{exerc:afnd2adf1},
\ref{exerc:afnd2adf2} e \ref{exerc:afnd2adf3} considerando agora as
seguintes expressões regulares:

\begin{enumerate}

\item ${\cal L} = (a + b)^* abb$

\item \label{exerc:convReais} ${\cal L}_{reais} = ('+'\ +\ '-')?\ d^*\ ('.')?\ d^+$

\end{enumerate}

\begin{code}


\end{code}

\end{exercicio}
%--------------------

\end{document}