


\section{Présentation}

Dans la définition de la syntaxe d'un langage de programmation, par exemple, on rencontre souvent des définitions telles que celle d'un identificateur :

\og  Un identificateur est un identificateur de symbole ou un identificateur de variable ; un identificateur de symbole commence par deux caractères alphabétiques, suivi par un nombre quelconque, éventuellement nul, de chiffres, suivis, etc.\fg{}  \\

Il s'agit ici d'introduire des abréviations pour ce type d'expressions ; ces abréviations conduisent à la notion d'expression rationnelle.

\begin{Ex}
 L'expression rationnelle $a(a|b)^*$ signifie : un caractère $a$, suivi d'un nombre quelconque, éventuellement nul, de caractères choisis dans l'ensemble $\{a,b\}$.
\end{Ex}


Un langage est évidemment associé à une expression rationnelle. On notera $\mathcal{L}(r)$ le langage associé à l'expression rationnelle $r$.

\begin{Exo}
Quel est le langage décrit par l'expression rationnelle $\alpha = (ab^*)^*$ ?

L'expression $\beta = a(a|b)^*$ est-elle équivalente à $\alpha$ ?

Trouvez une expression équivalente à $\alpha$ dans laquelle il n'y a qu'une $*$.
\end{Exo}

\noindent \emph{\underline{Réponse : }} $\varepsilon \in L_\alpha \setminus L_\beta$ ; expression équivalente : $(\varepsilon|a(a|b)^*)$.\\


Définissons dorénavant plus rigoureusement cela, rentrons dans les détails...

\section{Règles de définition}

Voici les règles qui permettent de définir les expressions rationnelles sur un alphabet $\Sigma$ :\\

\begin{enumerate}
 \item $\varepsilon$ est une expression rationnelle qui dénote $\{$ \og \fg{} $\}$ (l'ensemble constitué de la chaîne vide).
 \item Si $r$ et $s$ dénotent les langages $\mathcal{L}(r)$ et $\mathcal{L}(s)$, alors

\begin{itemize}
 \item $(r)|(s)$ désigne le langage $\mathcal{L}(r) \cup \mathcal{L}(s)$ (\emph{i.e.} le langage obtenu par réunion des deux langages $\mathcal{L}(r)$ et $\mathcal{L}(s)$).
 \item $(r)(s)$ désigne le langage $\mathcal{L}(r) \mathcal{L}(s)$ (\emph{i.e.} le langage obtenu en concaténant, de toutes les manières possibles, un mot du langage $\mathcal{L}(r)$ et un mot du langage $\mathcal{L}(s)$).
 \item $(r)^*$ désigne le langage $\left( \mathcal{L}(r) \right)^*$ (\emph{i.e.} le langage constitué de la chaîne vide, des mots de $\mathcal{L}(r)$ et des mots obtenus en concaténant un nombre quelconque (au moins deux) de mots de $\mathcal{L}(r)$).
 \item $(r)$ désigne le langage $\mathcal{L}(r)$.
\end{itemize}
\end{enumerate}


\begin{Exo}
Décrire, sur l'alphabet \{ Acquérir, Sortir, Rentrer, Vendre, Archiver \}, la vie d'un document dans une bibliothèque.
\end{Exo}


\noindent \emph{\underline{Réponse : }} Acquérir (Sortir Rentrer )* (Sortir | Vendre | Archiver).

\begin{Exo}
\'Ecrire, en syntaxe BNF, la grammaire algébrique de toutes les expressions rationnelles sur $\Sigma$.
\end{Exo}


\noindent \emph{\underline{Réponse : }} \\
\begin{tabular}{lll}
$<$ expression $>$ & ::= & $<$ primitive $>$\\
                   & ::= & $<$ parenthèse $>$\\
                   & ::= & $<$ concaténation $>$\\
                   & ::= & $<$ étoile $>$\\
$<$ primitive $>$  & ::= & $\varepsilon$\\
                   & ::= & $x$ (avec $x \in \Sigma$)\\
$<$ parenthèse $>$ & ::= & '(' $<$ expression $>$ $|$ $<$ expression $>$ $<$ suite $>$ ')'\\
$<$ suite $>$      & ::= & $<$ expression $>$ $<$ suite $>$\\
                   & ::= &\\
$<$ concaténation $>$ & ::= & $<$ expression $>$ $<$ expression $>$\\
$<$ étoile $>$     & ::= & $<$ primitive $>$ '*'\\
                   & ::= & $<$ parenthèse $>$ '*'\\ 
                   & ::= & $<$ concaténation $>$ '*'\\ 
\end{tabular}

\bigskip

On peut réduire le nombre de paires de parenthèses écrites, en adoptant les règles de priorité suivantes :

\begin{itemize}
\item La répétition est prioritaire sur tout autre opérateur.

Autrement dit $ab^*$ est $a|b^*$ doivent être interprétés (respectivement) par $a(b)^*$ et $a|(b^*)$.

\item La concaténation est prioritaire sur l'alternative.

$rs|tu$ doit donc être interprété comme $(rs)|(tu)$.
\end{itemize}

\bigskip

De plus, on admettra l'écriture $a^n$ pour le mot $aaa \hdots aa$ ($n$ fois).



\begin{Exo}
Soit l'alphabet $\Gamma = \{+,\times,a,b,c\}$. Repérer les expressions rationnelles sur $\Gamma$ parmi les suites de symboles suivantes :
\begin{enumerate}
\item $(a|+)^*+b\times c*$,
\item $+^*|^*\times^*$,
\item $((a+)^*|)b^*c$,
\item $((a^*b)^*\times |ca+^*)$.
\end{enumerate}
\end{Exo}


\noindent \emph{\underline{Réponse : }} Seules la première et la dernière suite de symboles sont des expressions rationnelles.


\section{Propriétés des opérateurs}



\begin{Th}
Les propriétés de ces opérateurs sont les suivants :

\begin{enumerate}
 \item Associativité : $r|(s|t) = (r|s)|t$ et $r(st) = (rs)t$.
 \item Commutativité de l'alternative : $r | s = s | r$.
 \item Distributivité de l'alternative sur la concaténation : $r(s|t) = rs|rt$ et $(r|s)t = rt|st$.
 \item $\epsilon$ est élément neutre pour la concaténation.
 \item La répétition est idempotente : $r^{**}=r^*$.
\end{enumerate} 
\end{Th}


\begin{Exo}
Quel est le langage sur $\{a,b\}$ décrit par l'expression rationnelle : $b^*a(b^*ab^*a)^*b^*$ ? En trouver une \og meilleure \fg{} expression.
\end{Exo}


\noindent \emph{\underline{Réponse : }} L'ensemble des mots sur $\{a,b\}$ contenant un nombre impair de $a$. $b^* a(b|ab^*a)^*$.

\section{De nouvelles abréviations}

D'autres abréviations peuvent être introduites :

\begin{itemize}
 \item L'opérateur de fermeture positive : $a^+$ désigne \og au moins une instance de\fg{}  (\emph{i.e.} $a^+ = a a^*$
 \item L'opérateur ? qui signifie \og  zéro ou une occurence de\fg{}  (\emph{i.e.}  $a? = a|\epsilon$).
 \item Classes de caractères : la notation $[abc]$ est une autre notation pour $a|b|c$, sans intéret, sauf dans le cas de $[a-z] = a|b|\hdots |z$.
\end{itemize}

\begin{Ex}
 On peut représenter \og  une lettre, suivie d'un nombre quelconque, éventuellement nul, de lettres ou de chiffres\fg{}  par $[a-zA-Z][a-zA-Z0-9]^*$.
\end{Ex}

\section{Universalité des expressions rationnelles}

Les expressions rationnelles ne sont pas universelles, et ne permettent pas de décrire tous les langages.

\begin{Ex}
Il est impossible de décrire, à l'aide d'expression rationnelles, le langage défini par
$$\{ wcw | w \text{ est une chaîne de a et de b} \}$$
\end{Ex}

En effet, \og une chaîne de $a$ ou de $b$\fg{}  peut s'exprimer par l'expression rationnelle $(a|b)^*$.

Mais, si l'on écrit ensuite $(a|b)^* c (a|b)^*$, la syntaxe des expressions rationnelles ne permet pas de préciser que les chaînes qui précèdent et suivent le $c$ sont identiques.


\gsaut
\centerline{\x{Fin du Chapitre}}

