%
% 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 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º 1\\ (Expressões Regulares (1))}
\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 mp303f01.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 mp303f01.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{Expressões Regulares}
%--------------------
\begin{exercicio} 
Escreva expressões regulares para definir formalmente as 
\textit{linguages regulares} a seguir descritas pelas frases que as
constituem:

\begin{enumerate}

\item Linguagem cujas frases s\~ao constituídas por zero ou mais símbolos $a$ seguidos por 
um ou mais símbolos $b$.

\item Linguagem cujas frases, não vazias, s\~ao constituídas por símbolos $a$ ou $b$ sem misturas.

\item Linguagem cujas frases, não vazias, s\~ao constituídas por símbolos $a$ ou $b$ em qualquer combina\c c\~ao.

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

\end{exercicio}
%--------------------
\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}
%--------------------

\section{Expressões Regulares em \hask}
%--------------------
\begin{exercicio}
Defina o tipo de dados algébrico \texttt{RegExp} em \hask\ para
representar expressões regulares.

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

module RegExp where


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

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

\begin{code}





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

\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 \hask\ no exercício
anterior obtém-se:

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

\begin{code}





\end{code}
\end{exercicio}
%--------------------
\newpage
\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 \hask\ (tipo de dados e funç~ao showRE) para permitir escrever expressões usando esta notação.

\begin{code}



\end{code}

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



\end{code}

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

\end{document}