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


\def\Ipe#1{\def\IPEfile{#1}\input{#1}}
\def\hask{\textsf{Haskell}}
\def\hugs{\textsf{Hugs}}

\newenvironment{code}
{\vspace{0.3cm}
\textbf{Código hHaskell} \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º 3\\ (Autómatos Deterministas)}
\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 mp302f03.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 mp302f03.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{Autómatos Finitos Deterministas}

\begin{exercicio} 
Defina um autómato finito determinista para cada uma das seguintes linguagens
regulares:

\begin{enumerate}
\item $ a\ +\ ab\ +\ abc$
\item $a^+\  b^*$
\item $(\ aa\ )^*$
\item $1^*\  (\ 0\ +\ 0 1\ )^*$
\end{enumerate}
\end{exercicio}
%--------------------

\section{Autómatos Finitos Deterministas em \hask}

\begin{exercicio}
Escreva em \hask\ o tipo de dados que modela um autómato finito 
determinista.

\begin{code}
--
-- Módulo de Autómatos Finitos Deterministas em Haskell
--
-- Métodos de Programação III
-- 2001/2002
--

module Dfa where

import RegExp

data Dfa =


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

\begin{exercicio} 
Defina em \hask\ as seguintes funções sobre autómatos finitos deterministas:

\begin{enumerate} 

\item Função \texttt{dfawalk} que "caminha" num autómato finito
determinista, a partir dum certo estado, "consumindo" os símbolos de uma string dada.\\
A função recebe como argumentos a função de transição de
estados do autómato, o estado de partida e a string a processar e dá como
resultado o estado atingido após consumir todos os símbolos da string.

\begin{code}

-- dfawalk ::


\end{code}

\item Função \texttt{dfaaccept} que, dado um autómato e uma string,
indica se a string pertence à linguagem definida pelo autómato.

\begin{code}

-- dfaaccept ::

\end{code}

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

\begin{exercicio}
Recorde a matéria de \textsf{Métodos de Programação I} e mostre que a função
\texttt{dfaaccept} pode ser escrita como um catamorfismo, mais
precisamente recorrendo à função (pre-definida) \texttt{foldl}
("folding" a partir da esquerda).

\begin{verbatim}
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f st [] = st
foldl f st (x:xs) = foldl f (f st x) xs 
\end{verbatim}

\begin{code}


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

\begin{exercicio} 
Considere o seguinte autómato finito determinista 
${\cal A}_1 = ({\cal V},{\cal Q},{\cal S}, {\cal
Z}, {\cal \delta})$, com ${\cal V} = \{ a,b,c \}$,
${\cal Q} = \{ 1,2,3,4\}$, $ {\cal S} = 1$, ${\cal Z} = \{ 4 \}$ e
\begin{center}
\begin{tabular}[t]{l}
$\delta$  1 a =  2 \\
$\delta$  1 c =  4 \\
$\delta$  2 b =  3 \\
$\delta$  3 c =  4 \\
$\delta$  4 c =  4 \\
\end{tabular}
\end{center}

\noindent Modele este autómato em \hask 

\begin{code}

-- a_1 = 

\end{code}

\noindent e então responda às seguintes perguntas:

\begin{enumerate}
\item $"abcc" \in {\cal L} ({\cal A}_1)$?

\item Qual o estado atingido processando a string \texttt{"ab"} e
partindo do estado $1$?

\item A string \texttt{"aba"} pertence à linguagem ${\cal L} ({\cal
A}_1)$?  Qual o resultado produzido pela função \texttt{dfaaccept}?
Como pode ser resolvido este "problema"?
\end{enumerate}
\end{exercicio}
%--------------------

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

Prove que a expressão regular $p = abc^* + c$ e o autómato finito
determinista ${\cal A}_1$ não definem a mesma linguagem, i.e., ${\cal
L} (p) \neq {\cal L} ({\cal A}_1)$. Recorra à implementação em
\hask\ para efectuar a prova.

\begin{code}


\end{code}
\end{exercicio}
%--------------------
\newpage
\section{AFD para a linguagem dos números reais}

\begin{exercicio} 
Considere a linguagem dos números reais definida
pela seguinte expressão regular:

\[
(\texttt{'+'} + \texttt{'-'})? ~  digit^* ~  (\texttt{'.'})? ~ digit^+ 
\]

\begin{enumerate}
\item
Modele esta linguagem em \hask\ como uma expressão regular e como um
autómato finito determinista.

\begin{code}


\end{code}
\item
Verifique se a string
\texttt{"+123.3456"} pertence à linguagem, utilizando as funções
\texttt{matches'} e \texttt{dfawalk}, respectivamente.
\item 
Indique qual
das duas funções é mais eficiente a produzir o resultado, utilizando
para tal o número de reduções efectuado pelo interpretador \hugs.
\end{enumerate}
\end{exercicio}
%--------------------

\end{document}