\documentclass{tpcaml}

\tp{2}{Expressions Rationelles}

\begin{document}

\maketitle

On manipule ici des \textbf{mots}, qui sont des suites finies de lettres
d'un \textbf{alphabet}. Par exemple, $car$ est un mot sur l'alphabet
latin. On appelle \textbf{facteur} d'un mot tout 
mot qui apparaît tel quel dans celui-ci. Par exemple $car$ est un
facteur de $decarcasser$. Il existe un unique mot ne contenant
aucune lettre, appelé le mot vide et noté $\varepsilon$. 

\section{Mots et facteurs}

En Caml Light, on représente les mots par le type \verb+string+ des chaînes
de caractères. En particulier, \verb+a^b+ représente la concaténation, et
\verb+sub_string a i l+ représente le facteur $a_i\ldots a_{i+l-1}$.

\begin{codesection}
  type mot = \{ \+\\
    lettres : string ; \\
    debut : int ; fin : int \-\\
  \}
\end{codesection}

Dans cet exercice, on va avoir besoin de travailler de manière importante
sur les facteurs d'un mot. Pour gagner en performance, on va représenter
les facteurs d'un mot non pas avec le type \verb+string+, mais avec le
type \verb+mot+ ci-contre: le facteur est déterminé par le mot entier, 
la lettre de début, et la lettre de fin (exclue). 

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+mot+ qui représente un mot complet 
  à l'aide de ce type (en observant que tout mot est facteur de lui-même). 
  Elle est de type \verb+string -> mot+.
\end{question}
\vspace{12pt}

L'intérêt de cette représentation est que couper un facteur en deux est
très rapide (il n'implique pas de recopier les lettres du facteur). 

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+couper f i+ qui coupe le facteur $f$
  au niveau de la lettre $i$ du mot complet. Ainsi, si l'on coupe
  $f_a\ldots f_{b-1}$, on obtiendra le mot $f_a\ldots f_{i-1}$ 
  et le mot $f_i\ldots f_{b-1}$. Cette fonction est de type
  \verb+mot -> int -> mot * mot+. 
\end{question}

\section{Reconnaissance}

Un \textbf{langage} est un sous-ensemble de ${\cal A}^*$. La représentation 
informatique usuelle d'un langage $L$ se fait à travers une fonction de
reconnaissance $f : {\cal A}^* \rightarrow \{v,f\}$ telle que $L =
f^{-1}(v)$ (autrement dit, la fonction renvoie vrai si le mot fourni est
dans le langage, et faux sinon). 
 
On va travailler ici avec des fonctions de reconnaissance, dont le type
sera donc \verb+mot -> bool+. 

\subsection{Langage Singleton}
\begin{question}
  \'Ecrire la fonction \verb+facteur(f)+ qui reconnaît le langage
  singleton $\{f\}$ ne contenant que le mot $f$, de type 
  \verb+string -> mot -> bool+. 

  On appelle \verb+let vide = facteur ""+.

  On appelle \verb+let rien = fun _ -> false+.
\end{question}

\subsection{Langages Finis}

Si $L_1$ et $L_2$ sont des langages reconnus par les fonctions $f_1$ et
$f_2$, alors on note $f_1|f_2$ la fonction reconnaissant le langage
$L_1\cup L_2$. 

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+ou a b+ qui renvoie la fonction $a|b$, 
  où $a$ et $b$ sont des fonctions de reconnaissance. 
\end{question}
\vspace{12pt}

À l'aide des fonctions \verb+facteur+ et \verb+ou+, on peut construire
une fonction pour reconnaître n'importe quel langage fini.

\subsection{Langages Rationnels}

Si $L_1$ et $L_2$ sont des langages, on définit le langage concaténé:
\[L_1L_2 = \{ ab : a \in L_1, b \in L_2 \}\]
On note par ailleurs $f_1f_2$ la fonction de reconnaissance de ce langage. 

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+puis a b+ qui renvoie la fonction $ab$, 
  où $a$ et $b$ sont des fonctions de reconnaissance.
\end{question}
\vspace{12pt}

Si $L$ est un langage, on note $L^0 = \{\varepsilon\}$, $L^1 = L$, 
$L^2 = LL$ et plus généralement $L^n$ la concaténation appliquée $n$ fois
au même langage.

On définit alors l'étoile:
\[L^* = \cup_{i=0}^\infty L^i\]

\vspace{12pt}
\begin{question}
  Montrer que cette notation est cohérente si l'on considère ${\cal A}$
  comme l'ensemble des mots à une seule lettre.
\end{question}
\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+etoile a+ qui renvoie la fonction $a^*$, 
  où $a$ est une fonction de reconnaissance.
\end{question}
\vspace{12pt}

L'ensemble des langages que l'on peut reconnaître à l'aide des seules 
fonctions définies dans cet énoncé est appelé ensemble des 
\textit{langages rationnels}.


\section{Expressions Régulières}

Puisque toute fonction reconnaissant un langage rationnel peut être
construite à l'aide de ces opérations, on peut représenter le langage de
manière simplifiée par la suite des opérations à accomplir pour créer sa
fonction de reconnaissance.

On appelle alors expression régulière tout objet de la forme:
\[e = \left\{
\begin{array}{ll}
  \emptyset & \mathrm{Rien} \\
  \varepsilon & \mathrm{Vide} \\
  a \in {\cal A} & \mathrm{Lettre} \\
  e|e & \mathrm{Alternative}\\
  ee & \mathrm{Concatenation} \\
  e^* & \mathrm{Etoile} 
\end{array}
\right.\]

Chaque expression régulière reconnaît un langage rationnel, et chaque
langage rationnel est reconnu par une expression régulière. 

\vspace{12pt}
\begin{question}
  Le langage des mots sur l'alphabet $\{a,b\}$ qui ne contiennent pas deux
  $b$ consécutifs est-il un langage rationnel? Qu'en est-il du langage des
  mots de la forme $a^nb^n$?
\end{question}

\section{Ouvertures}

Parmi les questions auxquelles on répond en général sur les langages:

\paragraph{Un langage $L$ est-il rationnel?}
Si oui, on exhibe l'expression
régulière ou l'\em automate \em le reconnaissant. Si non, on utilise le \em
lemme de l'étoile\em. Dans les deux cas, on peut utiliser les \em
résiduels\em.

\paragraph{Comment améliorer la vitesse de reconnaissance?}
Actuellement très faible en cas de concaténation ou d'étoile (temps
quadratique, voire pire). On utilise des \em automates\em qui reconnaissent
ou rejettent un mot en temps linéaire, en les construisant rapidement grâce
à l'algorithme de \em Thompson\em.

\end{document}