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

\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 Finitos -- Cálculo Parcial)}
\date{Ano lectivo 2002/2003}
%\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 mp302f08.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 mp302f08.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{Cálculo Parcial de Autómatos Finitos}

\begin{exercicio} \label{exerc:afnd2adf1} 

Considere a linguagem regular ${\cal L}$ modelada pelas seguinte
expressão regular $p$:

\[
p = (a + b)^* ba
\]

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})$.

\item Represente a expressão regular $p$, e os autómatos finitos
${\cal A}_{nd}$ e ${\cal A}_{d}$ em Haskell. Usando o interpretador
Hugs, verifique qual dos reconhecedores, baseados nos modelos usados,
é mais eficiente a reconhecer a frase $"aabbabba"$

\end{enumerate}

\medskip

\begin{code}

import RegExp
import Dfa
import Ndfa

\end{code}

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

\begin{exercicio} 
Considere a definição em Haskell de um autómato finito determinista:

\begin{code}
dfa_A_6 = Dfa ['a','b','c'] ['A','B','C'] 'A' ['A','B','C'] delta
   where 
        delta 'A' 'a' = 'B'
        delta 'B' 'a' = 'B'
        delta 'B' 'b' = 'B' 
        delta 'B' 'c' = 'C'
\end{code}

Especialize o reconhecedor de autómatos finitos deterministas
\texttt{dfaaccept} para este autómato. Por outras palavras, cálcule
parcialmente a função \texttt{dfaaccept\ dfa\_A\_6}. Indique (usando o
interpretador Hugs) se o reconhecedor especializado para este autómato
é mais eficiente que o reconhecedor \texttt{dfaaccept} a processar a
frase $"aabbbbc"$.

\begin{code}



\end{code}

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

\begin{exercicio} 
Considere a definição em Haskell de um autómato finito não determinista:

\begin{code}
ndfa_A_6 = Ndfa ['a','b','c'] ['A','B','C','D'] ['A'] ['D'] delta
   where 
        delta 'A' (Just 'a') = ['B']
        delta 'A' Nothing    = ['D']
        delta 'B' (Just 'a') = ['B']
        delta 'B' (Just 'b') = ['B']
        delta 'B' Nothing    = ['A','C'] 
        delta 'C' (Just 'c') = ['D']
\end{code}

\begin{enumerate}

\item Cálcule um autómato finito determinista que defina a mesma
linguagem. Modele esse autómato em Haskell.

\item Especialize o reconhecedor de autómatos finitos deterministas
\texttt{dfaaccept} para o autómato obtido na alínea anterior.

\item Especialize o reconhecedor de autómatos finitos não-deterministas
\texttt{ndfaaccept} para o autómato \texttt{ndfa\_A\_6}.

\item Compare a performance do interpretador Hugs no reconhecimento da
frase $"aabbbbc"$ usando os quatro reconhecedores construídos. Isto é,
os reconhecedores genéricos e os especializados.

\end{enumerate}

\begin{code}



\end{code}

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

\begin{exercicio} 
Considere a expressão regular que define a linguagem dos números reais:

\[
{\cal L}_{reais} = ('+' + '-')?\ digit^+\ ('.' digit^+)?
\]

e responda às seguintes perguntas:

\begin{enumerate} 

\item Cálcule o autómato finito não-determinista ${\cal A}_{nd}$ tal que
${\cal L}(reais) = {\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})$.

\item Especialize os reconhecedores \texttt{dfaaccept} e
\texttt{ndfaaccept} com os respectivos autómatos finitos. 

\item Usando o interpretador Hugs, verifique qual dos reconhecedores
é mais eficiente a reconhecer a frase $"153.148"$.

\end{enumerate}

\begin{code}



\end{code}

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

\end{document}