automates/ConstructionAutomatesFinis.tex

   1
   2
   3
   4
   5
   6 L'algorithme exposé ici est appelé \emph{algorithme de Thompson}\index{algorithme!de Thompson}. Il permet de construire un AFND à partir d'une expression rationnelle.
   7
   8 \section{Automates à transitions instantanées}
   9
  10 \begin{Def}[Transition instantanée]
  11 Une \emph{transition instantanée} \index{transition instantanée} est une é\-vo\-lu\-tion possible de l'automate d'un état vers un autre sans qu'aucune entrée ne soit produite.
  12 \end{Def}
  13
  14 Les automates à transitions instantanées interviennent dans l'algorithme de Thompson de construction automatique d'un automate reconnaissant le langage associé à une expression rationnelle...
  15
  16 \section{Données et résultat}
  17 \begin{description}
  18  \item[Données] une expression rationnelle $r$ sur un alphabet $\Sigma$.
  19  \item[Résultat] Un AFND $M$ tel que $\mathcal{L}(M) = \mathcal{L}(r)$, qui ne comporte qu'un seul état initial et un seul état d'acceptation...
  20  \end{description}
  21
  22 \section{Algorithme}
  23
  24 \begin{enumerate}
  25 \item Décomposer l'expression en ses sous-expressions.\\
  26
  27 \item En utilisant les règles (a) et (b) ci-dessous, construire un AFND pour les symboles terminaux de la grammaire ou la chaîne vide (si un même symbole $a$ apparaît plusieurs fois dans l'expression rationnelle, un AFND séparé est construit pour chacune de ses occurences).\\
  28
  29 \item Combiner ensuite récursivement les AFND de base en utilisant la règle (c) jusqu'à obtenir l'AFND pour l'expression rationnelle toute entière.
  30
  31 \begin{enumerate}
  32  \item Pour $< >$, construire l'AFND :
  33 \begin{center}
  34  \unitlength = 1mm
  35 \begin{picture}(57,21)(0,-21)
  36 \put(0,-21){}
  37 \node[NLangle=0.0,Nmarks=i](n12)(16.0,-12.02){d}
  38 \imark(n12)
  39
  40 \node[NLangle=0.0,Nmarks=r](n21)(48.0,-12.01){f}
  41 \rmark(n21)
  42
  43 \drawedge[ELdist=2.5](n12,n21){$\varepsilon$}
  44 \end{picture}
  45 \end{center}
  46
  47  \item Pour $a \in \Sigma$, construire l'AFND :
  48 \begin{center}
  49  \unitlength = 1mm
  50 \begin{picture}(57,21)(0,-21)
  51 \put(0,-21){}
  52 \node[NLangle=0.0,Nmarks=i](n12)(16.0,-12.02){d}
  53 \imark(n12)
  54
  55 \node[NLangle=0.0,Nmarks=r](n21)(48.0,-12.01){f}
  56 \rmark(n21)
  57
  58 \drawedge[ELdist=2.5](n12,n21){a}
  59 \end{picture}
  60 \end{center}
  61  \item Si $N(s)$ et $N(t)$ sont les AFND pour les expressions rationnelles $s$ et $t$,
  62 \begin{itemize}
  63  \item Pour $st$, on construit l'AFND :
  64 \begin{center}
  65 \unitlength = 1mm
  66 \begin{picture}(115,25)(0,-25)
  67 \put(0,-25){}
  68 \node[NLangle=0.0,Nmarks=i](n12)(16.0,-16.02){d}
  69 \imark(n12)
  70
  71 \node(n13)(60.0,-16.02){}
  72
  73 \node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(40.0,-16.02){N(s)}
  74
  75 \node[NLangle=0.0,Nmarks=r](n17)(104.0,-16.02){f}
  76
  77 \node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n16)(80.0,-16.02){N(t)}
  78 \end{picture}
  79 \end{center}
  80
  81 L'état initial de $N(t)$, qui est état d'acceptation pour $N(s)$, perd ce double caractère dans la nouvelle construction.
  82
  83 \item Pour $s|t$, on construit l'AFND
  84 \begin{center}
  85  \unitlength = 1mm
  86 \begin{picture}(121,49)(0,-49)
  87 \put(0,-49){}
  88 \node[NLangle=0.0,Nmarks=i](n12)(16.0,-28.01){d}
  89 \imark(n12)
  90
  91 \node(n13)(88.0,-40.01){}
  92
  93 \node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(64.0,-16.01){N(s)}
  94
  95 \node[NLangle=0.0,Nmarks=r](n17)(112.0,-28.01){f}
  96
  97 \node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n16)(64.0,-40.01){N(t)}
  98
  99 \node(n20)(40.0,-40.01){}
 100
 101 \node(n21)(40.0,-16.01){}
 102
 103 \node(n22)(88.0,-16.01){}
 104
 105 \drawedge[ELdist=2.5](n12,n21){$\varepsilon$}
 106
 107 \drawedge[ELside=r,ELdist=2.5](n12,n20){$\varepsilon$}
 108
 109 \drawedge[ELside=r,ELdist=2.5](n13,n17){$\varepsilon$}
 110
 111 \drawedge[ELdist=2.5](n22,n17){$\varepsilon$}
 112 \end{picture}
 113 \end{center}
 114
 115 Les états initiaux et les états d'acceptation des AFND de $N(s)$ et de $N(t)$ perdent leur caractère dans le nouvel AFND.
 116
 117 \item Pour l'expression rationnelle $s^*$, on construit l'AFND composé $N(s^*)$ :
 118
 119 \begin{center}
 120  \unitlength = 1mm
 121 \begin{picture}(125,57)(0,-57)
 122 \put(0,-57){}
 123 \node[NLangle=0.0,Nmarks=i](n12)(16.0,-28.01){d}
 124 \imark(n12)
 125
 126 \node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(64.0,-28.01){N(s)}
 127
 128 \node[NLangle=0.0,Nmarks=r](n17)(116.01,-28.01){f}
 129
 130 \node(n21)(40.0,-28.01){}
 131
 132 \node(n22)(88.0,-28.01){}
 133
 134 \drawedge[ELdist=2.5](n12,n21){$\varepsilon$}
 135
 136 \drawedge[ELdist=2.5](n22,n17){$\varepsilon$}
 137
 138 \drawbpedge[ELside=r,ELdist=2.5](n22,89,23.28,n21,87,23.3){$\varepsilon$}
 139
 140 \drawbpedge[ELside=r,ELdist=2.5](n12,-89,24.22,n17,-90,24.7){$\varepsilon$}
 141
 142 \end{picture}
 143 \end{center}
 144
 145
 146 Les états initiaux et les états d'acceptation de $N(s)$ perdent leurs qualités.
 147
 148 \item Pour une expression parenthésée $(s)$, utiliser $N(s)$ lui-même.
 149 \end{itemize}
 150
 151 \end{enumerate}
 152
 153 \end{enumerate}
 154
 155
 156 \section{Exemple}
 157
 158 On applique l'algorithme sur l'exemple : $(a^2|b^2)^*|(a^3|b^3)^*$.
 159
 160 \begin{center}
 161  \unitlength = 0.85mm
 162 \begin{picture}(182,119)(0,-119)
 163 \put(0,-119){}
 164 \node[NLangle=0.0,Nmarks=i](n0)(12.0,-52.0){0}
 165
 166 \node[NLangle=0.0](n2)(32.0,-76.0){11}
 167
 168 \node[NLangle=0.0](n3)(56.0,-28.0){2}
 169
 170 \node[NLangle=0.0](n5)(72.0,-16.0){3}
 171
 172 \node[NLangle=0.0](n6)(72.0,-40.0){6}
 173
 174 \node[NLangle=0.0](n7)(92.0,-40.0){7}
 175
 176 \node[NLangle=0.0](n8)(112.0,-40.0){8}
 177
 178 \node[NLangle=0.0](n9)(128.0,-28.0){9}
 179
 180 \node[NLangle=0.0](n10)(92.0,-16.0){4}
 181
 182 \node[NLangle=0.0](n11)(112.0,-16.0){5}
 183
 184 \node[NLangle=0.0](n12)(152.0,-28.0){10}
 185
 186 \node[NLangle=0.0](n13)(52.0,-76.01){12}
 187
 188 \node[NLangle=0.0](n14)(68.0,-64.01){13}
 189
 190 \node[NLangle=0.0](n15)(68.0,-88.01){17}
 191
 192 \node[NLangle=0.0](n16)(84.0,-88.01){18}
 193
 194 \node[NLangle=0.0](n17)(100.0,-88.01){19}
 195
 196 \node[NLangle=0.0](n19)(84.0,-64.01){14}
 197
 198 \node[NLangle=0.0](n20)(100.0,-64.01){15}
 199
 200 \node[NLangle=0.0](n21)(152.0,-76.0){22}
 201
 202 \node[NLangle=0.0,Nmarks=r](n31)(172.0,-52.0){23}
 203
 204 \node[NLangle=0.0](n32)(32.0,-28.0){1}
 205
 206 \drawedge(n32,n3){$\varepsilon$}
 207
 208 \drawedge(n0,n32){$\varepsilon$}
 209
 210 \drawedge(n0,n2){$\varepsilon$}
 211
 212 \drawedge(n2,n13){$\varepsilon$}
 213
 214 \drawedge(n13,n14){$\varepsilon$}
 215
 216 \drawedge(n13,n15){$\varepsilon$}
 217
 218 \drawedge(n14,n19){a}
 219
 220 \drawedge(n15,n16){b}
 221
 222 \drawedge(n19,n20){a}
 223
 224 \drawedge(n16,n17){b}
 225
 226 \drawedge(n21,n31){$\varepsilon$}
 227
 228 \drawedge(n3,n5){$\varepsilon$}
 229
 230 \drawedge(n3,n6){$\varepsilon$}
 231
 232 \drawedge(n6,n7){b}
 233
 234 \drawedge(n7,n8){b}
 235
 236 \drawedge(n8,n9){$\varepsilon$}
 237
 238 \drawedge(n5,n10){a}
 239
 240 \drawedge(n10,n11){a}
 241
 242 \drawedge(n11,n9){$\varepsilon$}
 243
 244 \drawedge(n9,n12){$\varepsilon$}
 245
 246 \drawedge(n12,n31){$\varepsilon$}
 247
 248 \node[NLangle=0.0](n33)(116.0,-64.01){16}
 249
 250 \node[NLangle=0.0](n34)(116.0,-88.01){20}
 251
 252 \node[NLangle=0.0](n35)(132.0,-76.01){21}
 253
 254 \drawedge(n20,n33){a}
 255
 256 \drawedge(n17,n34){b}
 257
 258 \drawedge(n33,n35){$\varepsilon$}
 259
 260 \drawedge(n34,n35){$\varepsilon$}
 261
 262 \drawedge(n35,n21){$\varepsilon$}
 263
 264 \drawbpedge[ELdist=2.0](n35,-269,28.93,n13,89,27.99){$\varepsilon$}
 265
 266 \drawbpedge[ELdist=2.0](n9,-269,32.69,n3,89,32.22){$\varepsilon$}
 267
 268 \drawbpedge[ELside=r,ELdist=2.0](n2,-89,31.99,n21,-89,32.93){$\varepsilon$}
 269
 270 \drawbpedge[ELdist=1.5](n32,-89,28.69,n12,-89,28.22){$\varepsilon$}
 271
 272
 273
 274 \end{picture}
 275 \end{center}
 276
 277
 278
 279 \begin{Exo}
 280 On donne l'expression rationnelle $(a | b)^* | (a^2 | b^2)^*$.
 281
 282 Utiliser l'algorithme de Thompson pour obtenir un automate non déterministe, à transitions instantanées, reconnaissant le langage.
 283 \end{Exo}
 284
 285
 286 On rappelle que, par définition, sont accessibles sur une entrée donnée $x$ depuis un état donné $e$ : les états accessibles en effectuant successivement
 287 \begin{itemize}
 288 \item un nombre arbitraire (éventuellement nul) de transitions instantannées,
 289 \item une transition d'entrée $x$ et
 290 \item un nombre arbitraire (éventuellement nul) de transitions instantannées.
 291 \end{itemize}
 292
 293 \begin{Ex}
 294 Pour...
 295 \begin{itemize}
 296 \item L'état 3, avec entrée $a$ : on passe à l'état 4.
 297 \item Si l'entrée $a$ se produit au départ, les états accessibles sont $\{ 4, 14 \}$.
 298 \item Et, à partir de l'état 4 et de l'entrée $a$ : $\{ 5, 9, 2, 10, 23, 3, 6 \}$.\\
 299 \end{itemize}
 300 \end{Ex}
 301
 302 % La variable \og état initial \fg{} d'un automate de Thompson est constituée de l'état initial et de tous les états accessibles depuis celui-ci par un nombre quelconque de transitions instantannée :
 303 %
 304 % $$\{ 0, 1, 11, 2, 10, 12, 22, 3, 6, 13, 17, 23 \}$$
 305
 306
 307
 308 D'où l'algorithme suivant simplifiant l'automate de l'algorithme de Thompson...
 309
 310 \section{Finalisation}
 311
 312 L'automate construit par algorithme de Thompson n'est pas utilisable tel quel.\\
 313
 314 Il faut en supprimer les transitions instantanées, ce qui se fait par un algorithme voisin de la construction par sous-ensembles. Il faudra, par ailleurs, ensuite, le déterminiser et le minimiser.\\
 315
 316 Soit $M$ l'automate de Thompson obtenu par l'algorithme précédent, $E$ l'ensemble de ses états, $e \in E$ son (unique) état initial et $a \in E$ son (unique) état d'acceptation.\\
 317
 318 On remplace cet automate par un automate $\mathcal{M}$ qui reconnaît le même langage, dont l'ensemble des états est $\mathcal{E}$, l'état initial est $S$, et l'ensemble des états d'acceptation est $A \subset \mathcal{E}$ et qui est obtenu de la manière suivante :
 319
 320 \begin{itemize}
 321 \item $S$ est composé de $e$ et de tous les états de $M$ qui sont accessibles depuis $e$ par un nombre quelconque de transitions instantanées (éventuellement aucune). Dans l'exemple précédent, $$S = \{ 0, 1, 11, 2, 10, 12, 22, 3, 6, 13, 17, 23 \}$$.
 322
 323 \item Soit $Y \in \mathcal{E}$ une partie de l'ensemble des états, et $x$ une entrée. L'image $Y_x$ de $Y$  est constituée des états accessibles depuis un état quelconque de $Y$ par (exactement) une entrée $x$, suivie d'un nombre quelconque de transitions instantanées.
 324
 325 \item $A = \{ Y \in \mathcal{E} | Y \cap \{a\} \neq \emptyset \}$, à savoir les parties $Y$ ci-dessus définies de $E$ qui contiennent l'ancien état d'acceptation.
 326 \end{itemize}
 327
 328
 329 \begin{Exo}
 330 Finalisez l'automate de l'exercice précédent. Le déterminiser, puis obtenir l'automate minimal reconnaissant le même langage.
 331 \end{Exo}
 332
 333
 334 \begin{Exo}[Reprise d'un exercice précédent, version Thompson]
 335 Construire des automates de Moore reconnaissant les langages définis par les expressions rationnelles :
 336 \begin{enumerate}
 337  \item $(a|b)^* b (a|b)^*$
 338  \item $((a|b)^2)^* | ((a | b)^3)^*$
 339  \item $ba^*|ab|(a|bb)ab^*$.
 340 \end{enumerate}
 341 \end{Exo}
 342
 343
 344 \begin{Exo}
 345  Donner les automates finis minimaux (table de transition, diagrame) reconnaissant les langages associés aux expressions rationnelles suivantes :
 346 \begin{itemize}
 347  \item $(a|b)^* (aaa|bb)$
 348  \item $(a|bb)^* abb^*$
 349 \end{itemize}
 350 \end{Exo}
 351
 352 \gsaut
 353 \centerline{\x{Fin du Chapitre}}
 354