automates/expReg.tex

   1
   2
   3
   4 \section{Présentation}
   5
   6 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 :
   7
   8 \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{}  \\
   9
  10 Il s'agit ici d'introduire des abréviations pour ce type d'expressions ; ces abréviations conduisent à la notion d'expression rationnelle.
  11
  12 \begin{Ex}
  13  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\}$.
  14 \end{Ex}
  15
  16
  17 Un langage est évidemment associé à une expression rationnelle. On notera $\mathcal{L}(r)$ le langage associé à l'expression rationnelle $r$.
  18
  19 \begin{Exo}
  20 Quel est le langage décrit par l'expression rationnelle $\alpha = (ab^*)^*$ ?
  21
  22 L'expression $\beta = a(a|b)^*$ est-elle équivalente à $\alpha$ ?
  23
  24 Trouvez une expression équivalente à $\alpha$ dans laquelle il n'y a qu'une $*$.
  25 \end{Exo}
  26
  27 \noindent \emph{\underline{Réponse : }} $\varepsilon \in L_\alpha \setminus L_\beta$ ; expression équivalente : $(\varepsilon|a(a|b)^*)$.\\
  28
  29
  30 Définissons dorénavant plus rigoureusement cela, rentrons dans les détails...
  31
  32 \section{Règles de définition}
  33
  34 Voici les règles qui permettent de définir les expressions rationnelles sur un alphabet $\Sigma$ :\\
  35
  36 \begin{enumerate}
  37  \item $\varepsilon$ est une expression rationnelle qui dénote $\{$ \og \fg{} $\}$ (l'ensemble constitué de la chaîne vide).
  38  \item Si $r$ et $s$ dénotent les langages $\mathcal{L}(r)$ et $\mathcal{L}(s)$, alors
  39
  40 \begin{itemize}
  41  \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)$).
  42  \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)$).
  43  \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)$).
  44  \item $(r)$ désigne le langage $\mathcal{L}(r)$.
  45 \end{itemize}
  46 \end{enumerate}
  47
  48
  49 \begin{Exo}
  50 Décrire, sur l'alphabet \{ Acquérir, Sortir, Rentrer, Vendre, Archiver \}, la vie d'un document dans une bibliothèque.
  51 \end{Exo}
  52
  53
  54 \noindent \emph{\underline{Réponse : }} Acquérir (Sortir Rentrer )* (Sortir | Vendre | Archiver).
  55
  56 \begin{Exo}
  57 \'Ecrire, en syntaxe BNF, la grammaire algébrique de toutes les expressions rationnelles sur $\Sigma$.
  58 \end{Exo}
  59
  60
  61 \noindent \emph{\underline{Réponse : }} \\
  62 \begin{tabular}{lll}
  63 $<$ expression $>$ & ::= & $<$ primitive $>$\\
  64                    & ::= & $<$ parenthèse $>$\\
  65                    & ::= & $<$ concaténation $>$\\
  66                    & ::= & $<$ étoile $>$\\
  67 $<$ primitive $>$  & ::= & $\varepsilon$\\
  68                    & ::= & $x$ (avec $x \in \Sigma$)\\
  69 $<$ parenthèse $>$ & ::= & '(' $<$ expression $>$ $|$ $<$ expression $>$ $<$ suite $>$ ')'\\
  70 $<$ suite $>$      & ::= & $<$ expression $>$ $<$ suite $>$\\
  71                    & ::= &\\
  72 $<$ concaténation $>$ & ::= & $<$ expression $>$ $<$ expression $>$\\
  73 $<$ étoile $>$     & ::= & $<$ primitive $>$ '*'\\
  74                    & ::= & $<$ parenthèse $>$ '*'\\
  75                    & ::= & $<$ concaténation $>$ '*'\\
  76 \end{tabular}
  77
  78 \bigskip
  79
  80 On peut réduire le nombre de paires de parenthèses écrites, en adoptant les règles de priorité suivantes :
  81
  82 \begin{itemize}
  83 \item La répétition est prioritaire sur tout autre opérateur.
  84
  85 Autrement dit $ab^*$ est $a|b^*$ doivent être interprétés (respectivement) par $a(b)^*$ et $a|(b^*)$.
  86
  87 \item La concaténation est prioritaire sur l'alternative.
  88
  89 $rs|tu$ doit donc être interprété comme $(rs)|(tu)$.
  90 \end{itemize}
  91
  92 \bigskip
  93
  94 De plus, on admettra l'écriture $a^n$ pour le mot $aaa \hdots aa$ ($n$ fois).
  95
  96
  97
  98 \begin{Exo}
  99 Soit l'alphabet $\Gamma = \{+,\times,a,b,c\}$. Repérer les expressions rationnelles sur $\Gamma$ parmi les suites de symboles suivantes :
 100 \begin{enumerate}
 101 \item $(a|+)^*+b\times c*$,
 102 \item $+^*|^*\times^*$,
 103 \item $((a+)^*|)b^*c$,
 104 \item $((a^*b)^*\times |ca+^*)$.
 105 \end{enumerate}
 106 \end{Exo}
 107
 108
 109 \noindent \emph{\underline{Réponse : }} Seules la première et la dernière suite de symboles sont des expressions rationnelles.
 110
 111
 112 \section{Propriétés des opérateurs}
 113
 114
 115
 116 \begin{Th}
 117 Les propriétés de ces opérateurs sont les suivants :
 118
 119 \begin{enumerate}
 120  \item Associativité : $r|(s|t) = (r|s)|t$ et $r(st) = (rs)t$.
 121  \item Commutativité de l'alternative : $r | s = s | r$.
 122  \item Distributivité de l'alternative sur la concaténation : $r(s|t) = rs|rt$ et $(r|s)t = rt|st$.
 123  \item $\epsilon$ est élément neutre pour la concaténation.
 124  \item La répétition est idempotente : $r^{**}=r^*$.
 125 \end{enumerate}
 126 \end{Th}
 127
 128
 129 \begin{Exo}
 130 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.
 131 \end{Exo}
 132
 133
 134 \noindent \emph{\underline{Réponse : }} L'ensemble des mots sur $\{a,b\}$ contenant un nombre impair de $a$. $b^* a(b|ab^*a)^*$.
 135
 136 \section{De nouvelles abréviations}
 137
 138 D'autres abréviations peuvent être introduites :
 139
 140 \begin{itemize}
 141  \item L'opérateur de fermeture positive : $a^+$ désigne \og au moins une instance de\fg{}  (\emph{i.e.} $a^+ = a a^*$
 142  \item L'opérateur ? qui signifie \og  zéro ou une occurence de\fg{}  (\emph{i.e.}  $a? = a|\epsilon$).
 143  \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$.
 144 \end{itemize}
 145
 146 \begin{Ex}
 147  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]^*$.
 148 \end{Ex}
 149
 150 \section{Universalité des expressions rationnelles}
 151
 152 Les expressions rationnelles ne sont pas universelles, et ne permettent pas de décrire tous les langages.
 153
 154 \begin{Ex}
 155 Il est impossible de décrire, à l'aide d'expression rationnelles, le langage défini par
 156 $$\{ wcw | w \text{ est une chaîne de a et de b} \}$$
 157 \end{Ex}
 158
 159 En effet, \og une chaîne de $a$ ou de $b$\fg{}  peut s'exprimer par l'expression rationnelle $(a|b)^*$.
 160
 161 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.
 162
 163
 164 \gsaut
 165 \centerline{\x{Fin du Chapitre}}
 166