% 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º 6\\ (Autómatos Não-Deterministas)}
\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 mp303f06.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 mp303f06.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 Não-Deterministas}

\begin{exercicio} \label{exerc:afnd1}
Defina um autómato finito não-determinista para as seguintes linguagens
regulares:

\begin{enumerate}
\item $b \ ((d + i);)^* \  e$
\item $(a + ab + \epsilon) \ a^* \ b^ +$
\item $a^* \ (b + \epsilon)^+ \ c^*$
\end{enumerate}

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

\begin{exercicio} \label{exerc:afnd2}
Considere a definição formal do seguinte autómato finito ${\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{center}
\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}
\end{center}

\medskip 
\noindent
e a definição formal da função $\epsilon\textit{-closure}$

\[
\begin{array}{l}
\epsilon\textit{-closure} :: ({\cal Q} \rightarrow ({\cal V}
 \cup \{ \epsilon \}) \rightarrow \{ {\cal Q} \}) \ \rightarrow\  \{ {\cal Q} \} \ \rightarrow\  \{ {\cal Q} \} \\
\epsilon\textit{-closure}\ \  \delta \ \  qs \  = \ 
qs \  \cup \  \bigcup_{q \in qs}
  \  (\epsilon\textit{-closure} \ \ \delta \ \ (\delta\ \ q\ \  \epsilon)) \\
\end{array}
\]

\noindent Responda, então, às seguintes perguntas:

\begin{enumerate}

\item Indique qual o tipo de não-determinismo que o autómato ${\cal
A}_2$ contém.

\item Calcule ($\epsilon\textit{-closure} \  \delta_2 \  \{C\}$)

\item Calcule o $\epsilon\textit{-closure}$ dos estados iniciais dos
autómatos do exercício~\ref{exerc:afnd1}.

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

\newpage

\section{Autómatos Finitos Não-Deterministas em Haskell}

\begin{exercicio}
Complete em Haskell o tipo de dados que modela um autómato finito 
não-determinista.

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

module Ndfa where

import List
import Dfa                     

data Ndfa st sy = Ndfa                          -- Finite set of alfabet symbols
                                                -- Finite set of states
                                                -- The set of start states
                                                -- The set of final states
                       (   ->          -> [  ]) -- Transition Function
\end{code}
\end{exercicio}
%--------------------

\begin{exercicio}
Considere de novo o autómato ${\cal A}_2$, definido formalmente no
exercício~\ref{exerc:afnd2}.\\
Modele este autómato na linguagem Haskell de acordo com o tipo de dados definido para o efeito.

\begin{code}

-- ndfa_a2 = 

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

\begin{exercicio} 
Considere a seguinte implementação em Haskell da função
$\epsilon\textit{-closure}$.\\
Utilize a função \texttt{epsilon-closure} para provar que as
soluções do exercício~\ref{exerc:afnd2} estão correctas.

\begin{code}

delta' delta []       sy = []
delta' delta (st:sts) sy = (delta st sy) `union` (delta' delta sts sy)

limit :: Eq a => (a -> a) -> a -> a
limit f s | s == next = s
          | otherwise = limit f next
            where next = f s

epsilon_closure :: Ord st => (st -> Maybe sy -> [st]) -> [st] -> [st]
epsilon_closure delta = limit f
  where f sts = sort (sts `union` (delta' delta sts Nothing))

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

\begin{exercicio} 
Considere a seguinte definição formal de aceitação de uma frase por um
autómato finito não determinista:

\noindent Um autómato finito não-determinista ${\cal A} = ({\cal V},{\cal
Q},{\cal S},{\cal Z},{\cal \delta}$) aceita uma frase $\alpha \in {\cal
V}^*$ sse

\[
accept\ {\cal A}\ \alpha
\]

\noindent onde 

\[
\begin{array}{l}
accept \ \  (v,q,s,z,\delta) \ sy \ =\ 
(walk \ \  \delta \ \ 
(\epsilon\textit{-closure} \ \  \delta \ \  s) \ \  sy) \  \cap \  z \ \
 \neq \  \emptyset \\
\end{array}
\]

\noindent e

\[
\begin{array}{l}
walk \ \delta \ sts \ sy = 
\left\{
\begin{array}{ll}
sts & \textit{se}\  sy = \langle \rangle \\
walk \ \delta \ ( \epsilon\textit{-closure} \ \delta \ (\delta' \ \ \delta \ \  sts \ \  s_0)) \  \langle s_1\cdots s_n \rangle & \textit{se}\ sy = \langle s_0s_1\cdots s_n \rangle \\
\end{array}
\right.
\end{array}
\]

\noindent Responda, então, às seguintes perguntas:

\begin{enumerate}
\item Prove que $"abc" \in {\cal L} ({\cal A}_2)$.

\item Implemente estas funções em Haskell. 
\end{enumerate}

\begin{code}

-- ndfaaccept ::


-- ndfawalk 


\end{code}


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

\begin{exercicio}
Considere de novo o autómato ${\cal A}_2$ do
exercício~\ref{exerc:afnd2} e responda às seguintes perguntas:

\begin{enumerate} 

\item Verifique se $"bbb" \in {\cal L} ({\cal A}_2)$? Apresente os cálculos
necessários para responder a esta pergunta, isto é, faça o
"\textit{trace}" da função \texttt{ndfaaccept}.

\item Indique quais os estados atingidos processando a string \texttt{"abb"}, 
partindo dos estados iniciais?

\item Prove que o autómato finito determinista ${\cal A}_1$ da
ficha-teórico prática $nº3$ (exercício 1.5) e o autómato finito
não-determinista ${\cal A}_2$ não definem a mesma linguagem, i.e.,
${\cal L} ({\cal A}_1) \neq {\cal L} ({\cal A}_2)$. Recorra à
implementação em Haskell para efectuar a prova.
\end{enumerate}

\begin{code}


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

\end{document}