%
% 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
%  2000/2001
%


\documentclass[12pt]{article}
\usepackage{a4wide}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{color}
\usepackage{alltt}
\usepackage{portuges}

\usepackage[latin1]{inputenc}
\usepackage{latexsym}


\usepackage[dvips]{epsfig}
\usepackage{epic}
\usepackage{eepic}


\def\Ipe#1{\def\IPEfile{#1}\input{#1}}

\newenvironment{code}
{\textbf{Solução} \hspace{1cm} \hrulefill \\ 
\smallskip 
\begin{center}
\begin{minipage}{.80\textwidth} 
\begin{alltt}\small}
{\end{alltt}
\end{minipage}
\end{center}
\hrule\smallskip
}


\newtheorem{exercicio}{}[section]

\title{\sf Métodos de programação III \\
\begin{tabular}{c}
{\small LMCC \& LESI}, {\small Universidade do Minho} \\
{\small Ano lectivo 2000/2001}  \\
{\small Ficha Teórico-Prática N$º$1} \\ 
\end{tabular}
}

\author{}
\date{}


%-------------------- Inicio do Documento -------------------------------

\begin{document}

\maketitle


Este texto está escrito em \textbf{literate Haskell}. Isto é, pode ser
interpretado como um documento \LaTeX\ ou como um puro programa na
linguagem Haskell. O documento é obtido "compilando" este ficheiro em
\LaTeX: \texttt{latex ficha1.lhs}. O programa Haskell incluído neste
ficheiro é compilado/interpretado directamento pelos
compiladores/interpretadores de Haskell. Para isso o código Haskell
deve estar delimitado pelo comando \texttt{begin} e \texttt{end}
\texttt{code}. Responda às perguntas sobre Haskell neste próprio
ficheiro e assim produzir o programa e a sua documentação.



\section{Expressões Regulares}

\begin{exercicio} 
Escreva expressões regulares para definir as seguintes
\textit{linguages regulares}:

\begin{enumerate}

\item Frases constituídas por zero ou mais símbolos $a$ seguidos por 
um ou mais símbolos $b$.

\item Frases, não vazias, constituídas por símbolos $a$ ou $b$.

\item Linguagem cujas frases são os digitos.

\item Linguagem dos números inteiros.

\item Linguagem que define os identificadores de linguagens de programação. 
Considere que um identificador começa obrigatoriamente por uma letra
minúscula, e é seguida por letras ou digitos.

\item Linguagem dos números reais. Considere que $-3$, $+11.12$, $-.14$, 
$14$ são frases da linguagem. Porém, $+$ , $11.$ , $++12$ , $11.2.3$
não são frases desta linguagem.

\end{enumerate}


\begin{exercicio}
Prove que a frase \texttt{abbc} é uma frase da linguagem definida pela
seguinte expressão regular: $a + (a b^+ c + b^*)$
\end{exercicio}


\end{exercicio}



\section{Expressões Regulares em Haskell}


\begin{exercicio}
Defina o tipo de dados algébrico \texttt{RegExp} em Haskell para
representar expressões regulares.
\end{exercicio}

\begin{code}
--
-- Módulo de Expressões Regulares em Haskell
--
-- Métodos de Programação III
-- 2000/2001
--

module RegExp where


\end{code}


\begin{exercicio}
Escreva as expressões regulares do exercício 1 usando os construtores
do tipo \texttt{RegExp}.
\end{exercicio}

\begin{code}





\end{code}



\begin{exercicio}

Escreva um função \textit{showRE} que imprime uma expressão regular na
sua notação tradicional. Por exemplo, se fizer o \textit{showRE} em
Hugs da primeira expressão regular escrita em Haskell no exercício
anterior obtém-se:

\begin{verbatim}
RegExp> showRE zeroAsMoreBs
"((a)*(b(b)*))"
\end{verbatim}

\end{exercicio}

\begin{code}





\end{code}


\begin{exercicio}
Usualmente utiliza-se uma notação própria para definir algumas
construções que ocorrem frequentemente em expressões regulares. Por
exemplo, a expressão regular $aa^*$ é escrita como $a^+$, e $a +
\epsilon$ como a?. 

\begin{enumerate}

\item Re-escreva o código Haskell para permitir escrever expressões usando esta notação.

\item Re-escreva as expressões regulares que definem a linguagens dos números inteiros e reais.
  
\end{enumerate}

\begin{code}





\end{code}



\end{exercicio}





\end{document}