automates/AutomatesFinis.tex

   1
   2
   3 \section{Automates finis}
   4
   5
   6 \subsection{Introduction}
   7
   8 On va dégager dans ce paragraphe la notion de \emph{machine} comme modèle conceptuel pour la description de dispositifs informatiques aussi variés qu'un ordinateur entier, un logiciel ou un compilateur.
   9
  10 \begin{Def}[Machine]
  11 Une \emph{machine}\index{machine} est un dispositif doté d'un certain nombre d'états, susceptible d'évoluer d'un état à un autre en fonction de divers paramètres, comme le temps (la machine est alors dotée d'une machine interne).
  12
  13 Elle est de plus apte à communiquer avec l'extérieur : elle peut accepter des données en provenance de l'extérieur (des entrées) ou communiquer des résultats à l'extérieur (des sorties).
  14 \end{Def}
  15
  16 \begin{Exo}
  17 Donnez des exemples de machines.
  18 \end{Exo}
  19
  20
  21 \begin{Rem}
  22 \`A chaque instant, la condition interne de la machine, y compris la mémoire, constitue son état.
  23 \end{Rem}
  24
  25
  26 \subsection{Mécanismes}
  27
  28 C'est le type le plus simple de machine :
  29
  30 \begin{Def}[Mécanisme]
  31 Un \emph{mécanisme}\index{mécanisme} est totalement imperméable au monde extérieur, il n'accepte aucune entrée ni aucune sortie.
  32
  33 C'est une machine à nombre fini d'états, dont le comportement est gouverné uniquement par le temps, mesuré par une horloge interne.
  34 \end{Def}
  35
  36 \begin{Exo}
  37  Donner un exemple de mécanisme.
  38 \end{Exo}
  39
  40
  41 Un mécanisme peut être entièrement décrit par un couple $(E,t)$, où $E$ est un ensemble fini d'états et $t : E \rightarrow E$ est une fonction de transition des états.
  42
  43 \begin{Th}[Existence d'un cycle]
  44 Un mécanisme entre nécessairement dans une boucle infinie (on dit : \emph{un cycle} \index{cycle}).
  45 \end{Th}
  46
  47
  48 \noindent En effet, le nombre d'états est fini.
  49
  50
  51 \begin{Def}[\'Etat-repos]
  52 S'il existe un état $e \in E$ tel que $t(e)=e$, cet état est appelé \emph{état-repos} \index{état-repos}.
  53 \end{Def}
  54
  55
  56 \begin{Rem}
  57 Un mécanisme qui entre dans un tel état n'en sort évidemment plus.
  58 \end{Rem}
  59
  60
  61
  62 \begin{Ex}
  63  Un feu de circulation routière peut être décrit par un mécanisme à trois états : $V$, $O$ et $R$, donc $E=\{V,O,R\}$.
  64
  65 La fonction de transition des états est telle que $t(V)=O, t(O)=R$ et $t(R)=V$.
  66
  67 On peut représenter ce mécanisme par le graphe de transition des états
  68
  69 \begin{center}
  70 \unitlength = 1mm
  71 \begin{picture}(51,39)(0,-39)
  72 \put(0,-39){}
  73 \node[NLangle=0.0](n0)(12.0,-12.0){R}
  74
  75 \node[NLangle=0.0](n1)(44.0,-12.0){V}
  76
  77 \node[NLangle=0.0](n2)(28.0,-32.0){O}
  78
  79 \drawedge(n1,n2){}
  80
  81 \drawedge(n2,n0){}
  82
  83 \drawedge(n0,n1){}
  84
  85
  86
  87 \end{picture}
  88 \end{center}
  89
  90
  91 \noindent ou par la matrice booléenne $T$ représentant $t$ :
  92
  93 $$
  94 T = \left( \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right)
  95 $$
  96 \end{Ex}
  97
  98
  99 \begin{Exo}
 100 L'exemple précédent possède-t-il un cycle ? un état-repos ? Sinon, le modifier pour.
 101 \end{Exo}
 102
 103
 104
 105 \section{Automates finis à comportement déterminé}
 106
 107
 108 \subsection{Définition}
 109 \begin{Def}[Automate fini à comportement déterminé]
 110 On appelle \index{automate!fini!à comportement déterminé} \emph{automate fini à comportement déterminé}(AFD) tout triplet $(E,I,t)$, où
 111 \begin{itemize}
 112  \item $E$ est un ensemble fini (l'ensemble des \emph{états}),
 113  \item $I$ est le \emph{vocabulare} de l'automate : c'est l'ensemble fini des symboles admis en entrée,
 114  \item $t : E \times I \rightarrow E$ est la \emph{fonction de transition d'états} : si l'automate se trouve dans l'état $e \in E$, il réagit à l'entrée $i \in I$ en passant à l'état $t(e,i)$.
 115 \end{itemize}
 116
 117
 118 Pour $i \in I$, on définit la fonction $t_i : E \rightarrow E$ par $t_i(e) = t(i,e)$.
 119 \end{Def}
 120
 121
 122
 123 \begin{Ex}
 124  Soit $E=\{e_0,e_1\}$, $I=\{0,1\}$ et $t$ telle que
 125 \begin{enumerate}
 126  \item l'entrée 0 laisse inchangé chacun des états,
 127  \item l'entrée 1 échange les états.
 128 \end{enumerate}
 129
 130 Un tel dispositif, en électronique, est appelé un \emph{T-flip-flop} \index{T-flip-flop}, il est abondamment utilisé dans les ordinateurs...
 131
 132 \begin{center}
 133  \includegraphics[scale=0.6]{automates/AutomateFiniDeterministe.eps}
 134 \end{center}
 135
 136 La table qui donne les valeurs de la fonction $t$ est appelée \emph{table de transition d'états}\index{table de transition d'états} de l'automate considéré :
 137
 138 $$
 139  \begin{array}{c|cc} t & 0 & 1 \\ \hline e_0 & e_0 & e_1 \\ e_1 & e_1 & e_0 \end{array}
 140 $$
 141 \end{Ex}
 142
 143
 144 \begin{Exo}
 145 Représenter le graphe de l'automate fini $M$ dont la table de transition des états est
 146 $$\begin{array}{c|ccc}
 147    t & 0 & 1 & 2\\
 148 \hline
 149 r & s & r & u \\
 150 s & r & r & s \\
 151 u & u & r & u
 152   \end{array}
 153 $$
 154 \end{Exo}
 155
 156 \noindent Réponse :
 157
 158
 159 \begin{center}
 160 \unitlength = 1 mm
 161 \begin{picture}(99,36)(0,-36)
 162 \put(0,-36){}
 163 \node[NLangle=0.0](n0)(12.0,-20.0){u}
 164
 165 \node[NLangle=0.0](n1)(48.0,-20.0){r}
 166
 167 \node[NLangle=0.0](n2)(84.0,-20.0){s}
 168
 169 \drawedge[curvedepth=8.0](n0,n1){1}
 170
 171 \drawedge[curvedepth=8.0](n1,n2){0}
 172
 173 \drawedge[curvedepth=8.0](n2,n1){0,1}
 174
 175 \drawedge[curvedepth=8.0](n1,n0){2}
 176
 177 \drawloop(n0){0,2}
 178
 179 \drawloop(n1){1}
 180
 181 \drawloop(n2){2}
 182 \end{picture}
 183 \end{center}
 184
 185
 186 \begin{Exo}
 187
 188 \'Ecrire la table de transition d'états de l'automate dont le graphe est représenté dans la figure suivante :\\
 189
 190 \unitlength = 1mm
 191 \begin{center}
 192
 193 \begin{picture}(70,66)(0,-66)
 194 \put(0,-66){}
 195 \node[NLangle=0.0](n0)(12.02,-12.0){s}
 196
 197 \node[NLangle=0.0](n1)(40.02,-12.0){p}
 198
 199 \node[NLangle=0.0](n2)(40.02,-36.0){r}
 200
 201 \node[NLangle=0.0](n3)(12.02,-36.0){q}
 202
 203 \drawloop[ELdist=2.1,loopangle=135.0](n0){0}
 204
 205 \drawloop[ELdist=2.1,loopangle=40.03](n1){1}
 206
 207 \drawloop[ELdist=2.1,loopangle=-49.25](n2){0}
 208
 209 \drawloop[ELpos=40,ELdist=2.1,loopangle=220.49](n3){0,1}
 210
 211 \drawedge[ELdist=1.9](n0,n1){1}
 212
 213 \drawedge[ELdist=1.5](n1,n2){0}
 214
 215 \drawedge[ELdist=2.5](n2,n3){1}
 216 \end{picture}
 217 \end{center}
 218 \end{Exo}
 219
 220 \noindent Réponse :
 221 $$
 222 \begin{array}{c|cc}
 223   & 0 & 1\\
 224 \hline
 225 p & r & p \\
 226 q & q & q \\
 227 r & r & q \\
 228 s & s & p
 229 \end{array}
 230 $$
 231
 232 \subsection{Automates finis avec sorties (machines de Moore et de Mealy)}
 233
 234 \begin{Def}[Machine de Moore]
 235 Une \emph{machine de Moore} est un sextuplet $M=(E,I,t,e_0,V,g)$ tel que $(E,I,t)$ est un AFD, et
 236
 237 \begin{itemize}
 238  \item $e_0 \in E$ est un état appelé \emph{état initial}, dans lequel se trouve la machine au départ de chaque exécution.
 239  \item $V$ est un ensemble fini, dit \emph{ensemble des sorties},
 240 \item $g:t<E,I> \rightarrow V$, où $t<E,I>$ est l'image de $t$, est la \emph{fonction de sortie} telle que, chaque fois que la machine entre dans l'état $e$, elle produise la sortie $g(e) \in V$.
 241 \end{itemize}
 242 \end{Def}
 243
 244
 245
 246
 247 \begin{Ex}
 248 Ici, $E=\{e_0, e_1, e_2, e_3\}$, $I=\{0,1\}$, $V=\{a,b,c\}$, $t$ est donnée, soit par le graphe de l'automate :
 249
 250 \unitlength = 1mm
 251 \scriptsize
 252 \begin{center}
 253 \begin{picture}(72,60)(0,-60)
 254 \put(0,-60){}
 255 \node[NLangle=0.0,Nmarks=i](n1)(20.01,-12.0){$e_0$}
 256
 257 \node[NLangle=0.0](n2)(48.01,-12.0){$e_1$:a}
 258
 259 \node[NLangle=0.0](n3)(48.01,-36.0){$e_2$:c}
 260
 261 \node[NLangle=0.0](n4)(20.01,-36.0){$e_3$:b}
 262
 263 \drawedge[ELdist=2.8](n2,n3){0,1}
 264
 265 \drawedge[ELside=r,ELdist=2.0](n1,n4){1}
 266
 267 \drawedge[ELdist=2.0](n1,n2){0}
 268
 269 \drawedge[ELside=r,ELdist=2.8,syo=0.8,eyo=0.8](n3,n4){0}
 270
 271 \drawedge[ELside=r,ELdist=2.5](n4,n3){1}
 272
 273 \drawloop[ELdist=1.9,loopangle=-51.71](n3){1}
 274
 275 \drawloop[ELdist=2.1,loopangle=227.17](n4){0}
 276 \end{picture}
 277 \end{center}
 278
 279 \normalsize
 280 \noindent soit par la table de transition d'états
 281
 282 $$
 283  \begin{array}{c|cc} t & 0 & 1 \\ \hline e_0 & e_1 & e_3 \\ e_1 & e_2 & e_2 \\ e_2 & e_3 & e_2 \\ e_3 & e_3 & e_2 \end{array}
 284 $$
 285
 286 $g$ se lit dans le graphe : $g(e_1) = a, g(e_2) = c, g(e_3) = b$.
 287 \end{Ex}
 288
 289 \begin{Rem}
 290 Une telle machine est aussi appelée \emph{traducteur} \index{traducteur} (elle \og  traduit \fg{} l'entrée 0001001 en une sortie $acbcbbc$).
 291 \end{Rem}
 292
 293
 294 \begin{Def}[Machine de Mealy]
 295 On obtient une \emph{machine de Mealy} \index{machine!de Mealy} lorsque la sortie est déterminée, non pas par l'état atteint, mais par la transition d'états.
 296
 297 C'est donc un sextuplet $(E,I,t,e_0,V,h)$ où la fonction de sortie $h$ est une application de $E \times I$ vers $V$.
 298 \end{Def}
 299
 300
 301 \begin{Rem}
 302 Il est clair que, pour une machine de Moore $(E,I,t,e_0,V,g)$, on peut définir une machine de Mealy équivalente (c'est-à-dire qui produit la même sortie sur toute séquence d'entrée), en posant $h(e,i) = g(t(e,i))$, soit $h = g o t$.
 303
 304 Réciproquement, en introduisant au besoin des états supplémentaires, on montre qu'on peut remplacer toute machine de Mealy par une machine de Moore équivalente.
 305 \end{Rem}
 306
 307
 308
 309 Nous ne nous occuperons donc dans la suite que de machines de Moore.
 310
 311
 312 \subsection{Automates de Moore}
 313
 314
 315 \begin{Def}[Automate de Moore]
 316  Une machine de Moore telle que l'ensemble $V$ des sorties est réduit à la paire booléenne $\{FAUX, VRAI\}$ ou $\{0,1\}$,
 317 \begin{itemize}
 318  \item tout état qui donne lieu à FAUX est appelé \emph{état de rejet}\index{état!de rejet},
 319  \item tout état qui donne lieu à la sortie VRAI est appelé \emph{état d'acceptation} \index{état!d'acceptation}.
 320 \end{itemize}
 321
 322 \noindent est appelée \emph{automate de Moore}\index{automate!de Moore} ou \emph{machine d'acceptation}\index{machine!d'acceptation}.
 323 \end{Def}
 324
 325
 326 \begin{Rem}
 327 Inutile d'exhiber ici la fonction de sortie, il suffit de se donner l'ensemble $A$ des états d'acceptation, sous-ensemble de $E$.
 328
 329 Un automate de Moore est donc défini par le quintuplet $(E,I,t,e_0,A)$.
 330 \end{Rem}
 331
 332
 333
 334 Sur le graphe représentant un automate de Moore, on représentera un état d'acceptation en l'entourant d'un double cercle.
 335
 336 Les autres états (simplement cerclés) sont les états de rejet.
 337
 338
 339 \section{Langage associé à un automates de Moore}
 340
 341 \subsection{Définition du langage}
 342
 343 Soit $M$ un automate de Moore.\\
 344
 345 L'ensemble des entrées $I$ peut être considéré comme l'alphabet d'un système formel.
 346
 347 L'ensemble des \og  mots \fg{}  construits avec cet alphabet (suite d'éléments de l'alphabet) qui conduisent la machine à un état d'acceptation peut être considéré comme l'ensemble des formules bien formées de ce système formel.
 348
 349 \begin{Def}[Langage]
 350 Ce système formel constitue le \emph{langage  associé à l'automate} $M$.
 351 \end{Def}
 352
 353 \begin{Notation}
 354  $\mathcal{L}(M)$
 355 \end{Notation}
 356
 357 Réciproquement, étant donné un langage $\cal L$, on peut éventuellement construire un automate de Moore $M$ tel que le langage associé à $M$ soit $\cal L $ : $\mathcal{L} = \mathcal{L} (M)$.
 358
 359 \begin{Rem}
 360 Cela n'est pas possible pour tous les langages. Quand c'est possible, cet automate analyse les mots du langage.
 361 \end{Rem}
 362
 363
 364 \subsection{Exemple et exercices}
 365
 366
 367 \begin{Ex}
 368 Construction de l'automate qui reconnaît le langage défini par l'expression suivante...
 369
 370 Un mot du langage est constitué d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1.
 371
 372 \begin{center}
 373 \unitlength = 1mm
 374 \begin{picture}(70,67)(0,-67)
 375 \put(0,-67){}
 376 \node[NLangle=0.0,Nmarks=i](n0)(16.0,-20.0){$e_0$}
 377
 378 \node[NLangle=0.0,iangle=128.23](n1)(44.0,-20.0){$e_1$}
 379
 380 \node[NLangle=0.0](n2)(16.0,-44.0){$e_2$}
 381
 382 \node[NLangle=0.0,Nmarks=r](n3)(44.0,-44.0){$e_3$}
 383
 384 \drawloop[ELdist=2.0,loopangle=37.45](n1){0,1}
 385
 386 \drawloop[ELdist=2.2,loopangle=225.0](n2){0}
 387
 388 \drawedge[ELdist=2.8](n0,n1){1}
 389
 390 \drawedge[ELside=r,ELdist=2.7](n2,n3){1}
 391
 392 \drawedge[ELside=r,ELdist=3.4](n0,n2){0}
 393
 394 \drawedge[ELdist=2.0](n3,n1){0}
 395
 396 \drawloop[ELdist=2.0,loopangle=-38.44](n3){1}
 397
 398
 399
 400 \end{picture}
 401 \end{center}
 402 \end{Ex}
 403
 404
 405
 406 \begin{Exo}
 407  Décrire le langage $\mathcal{L}(M)$ de l'automate de Moore $M$ dont la table de transition des états est :
 408
 409 $$\begin{array}{c|cc}
 410    t & 0 & 1 \\
 411  \hline
 412 e_0 & e_1 & e_2 \\
 413 e_1 & e_1 & e_2 \\
 414 e_2 & e_2 & e_1 \\
 415   \end{array}
 416 $$
 417
 418 L'état initial est $e_0$ et le seul état d'acceptation est $e_2$.
 419 \end{Exo}
 420
 421 \noindent Réponse : Les mots corrects contiennent un nombre impair de 1.
 422
 423 \begin{Exo}
 424  Sur l'alphabet $I = \{0,1\}$, construire l'automate de Moore dont le langage est l'ensemble de tous les mots sur $I$ se terminant par 10.
 425 \end{Exo}
 426
 427
 428 \noindent Réponse :
 429
 430 \begin{center}
 431  \unitlength = 1mm
 432 \begin{picture}(85,33)(0,-33)
 433 \put(0,-33){}
 434 \node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}
 435
 436 \node[NLangle=0.0](n4)(48.0,-16.0){$e_1$}
 437
 438 \node[NLangle=0.0,Nmarks=r](n5)(76.0,-16.0){$e_2$}
 439
 440 \drawedge[curvedepth=8.0](n3,n4){1}
 441
 442 \drawedge[curvedepth=8.0](n4,n5){0}
 443
 444 \drawedge[curvedepth=5.0](n5,n4){1}
 445
 446 \drawedge[curvedepth=15.0](n5,n3){0}
 447
 448 \drawloop(n3){0}
 449
 450 \drawloop(n4){1}
 451 \end{picture}
 452 \end{center}
 453
 454
 455 \begin{Exo}
 456  Construire un automate de Moore dont l'alphabet est constitué des lettres du mot \og ALGUE\fg{}  qui reconnaît les mots contenant la sous-chaîne \og GEL\fg{}  (et seulement celle-ci).
 457 \end{Exo}
 458
 459 \noindent Réponse :
 460
 461 \begin{center}
 462  \unitlength = 1mm
 463 \begin{picture}(117,46)(0,-46)
 464 \put(0,-46){}
 465 \node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}
 466
 467 \node[NLangle=0.0](n4)(48.0,-16.0){$e_1$}
 468
 469 \node[NLangle=0.0](n5)(76.0,-16.0){$e_2$}
 470
 471 \drawedge[curvedepth=8.0](n3,n4){G}
 472
 473 \drawedge[curvedepth=8.0](n4,n5){E}
 474
 475 \drawedge[curvedepth=18.46](n5,n3){A,G,U,E}
 476
 477 \drawloop(n3){A,L,U,E}
 478
 479 \drawloop(n4){G}
 480
 481 \node[NLangle=0.0,Nmarks=r](n6)(104.0,-16.0){$e_3$}
 482
 483 \drawedge[ELside=r,ELdist=2.2,curvedepth=8.0](n4,n3){A,L,U}
 484
 485 \drawedge[curvedepth=8.0](n5,n6){L}
 486
 487 \drawloop(n6){A,L,G,U,E}
 488
 489
 490
 491 \end{picture}
 492 \end{center}
 493
 494
 495 \section{Automates finis à comportement non déterminé}
 496
 497
 498 \subsection{Définitions et exemples}
 499
 500 Les automates considérés jusqu'à présent ont un comportement complètement \og dé\-ter\-mi\-né \fg{} : pour chaque configuration état-entrée $(e,i) \in E \times I$, une et une seule transition d'état est fixée.
 501
 502 Cela résulte du fait qu'ils sont régis par une \emph{fonction} de transition d'états $t$ (de $E \times I$ dans $E$).\\
 503
 504 On peut imaginer des automates moins \og rigides \fg{}, pour lesquels, dans certaines configurations, plusieurs transitions d'états sont possibles ou, au contraire, aucune n'est prévue.
 505
 506 Pour un tel automate, qualifié de non-déterministe, $t$ n'est plus une fonction, mais une relation binaire quelconque. Ainsi...
 507
 508 \begin{Def}[Automate fini non déterministe]
 509 Un \emph{automate fini non déterministe}\index{automate!fini!non déterministe} à états d'acceptation est défini par $(E,I,t,S,A)$ où :
 510 \begin{itemize}
 511 \item $E$ est un ensemble (fini) d'états,
 512 \item $I$ est l'ensemble des entrées,
 513 \item $t$ est la relation de transition des états,
 514 \item $S$, partie de $E$, est l'ensemble des états initiaux,
 515 \item $A$, partie de $E$, est l'ensemble des états d'acceptation.
 516 \end{itemize}
 517 \end{Def}
 518
 519 \begin{Rem}
 520 Il se peut donc qu'une entrée puisse conduire un automate vers plusieurs états possibles ou qu'elle laisse l'automate indifférent.
 521 \end{Rem}
 522
 523 \begin{Ex}
 524
 525 Dans cet exemple, lorsque l'automate se trouve dans l'état $e_0$, l'entrée $a$ peut le faire passer dans l'état $e_1$ ou dans l'état $e_3$ et, lorsqu'il se trouve dans l'état $e_1$, rien n'est prévu pour l'entrée $b$.
 526
 527
 528 \begin{center}
 529 \unitlength = 1mm
 530 \begin{picture}(51,53)(0,-53)
 531 \put(0,-53){}
 532 \node[NLangle=0.0,Nmarks=i](n8)(12.01,-20.0){$e_0$}
 533
 534 \node[NLangle=0.0](n9)(36.01,-20.0){$e_3$}
 535
 536 \node[NLangle=0.0,Nmarks=r](n10)(36.01,-44.0){$e_2$}
 537
 538 \node[NLangle=0.0,Nmarks=ir](n11)(12.01,-44.0){$e_1$}
 539
 540 \drawedge[ELdist=2.2](n8,n9){a,b}
 541
 542 \drawedge[ELside=r,ELdist=2.1](n8,n11){a}
 543
 544 \drawedge[ELdist=2.0,sxo=0.9,exo=0.9](n11,n9){c}
 545
 546 \drawedge[ELdist=2.7,syo=0.9,eyo=0.9](n11,n10){c}
 547
 548 \drawedge[ELdist=2.4](n10,n11){c}
 549
 550 \drawloop[ELdist=2.2](n9){a,b,c}
 551
 552 \drawloop[ELdist=2.2,loopangle=270](n11){a}
 553
 554 \drawloop[ELdist=2.2](n10){a,b}
 555
 556
 557
 558 \end{picture}
 559
 560 \end{center}
 561
 562 Table de transitions
 563
 564 $$
 565  \begin{array}{c|ccc} t & a & b & c \\ \hline \{e_0\} & \{e_1, e_3\}  & \{e_3\} & \varnothing \\ \{e_1\} & \{e_1\} & \varnothing & \{e_2, e_3\} \\ \{e_2\} & \{e_2\} & \{e_2\} & \{e_1\} \\ \{e_3\} & \{e_3\} & \{e_3\} & \{e_3\} \end{array}
 566 $$
 567 \end{Ex}
 568
 569 Il est évidemment possible de concevoir des AFND produisant des sorties, et, en particulier, des états d'acceptation et de rejet. On admettra par ailleurs qu'il puisse y avoir, dans ces cas, plusieurs états initiaux possibles.\\
 570
 571 Soit alors $M=(E,I,t,S,A)$ un AFND.
 572
 573 \begin{Def}[entrée reconnue]
 574 On dit qu'une suite $w$ d'entrées est \emph{reconnue} \index{reconnue} par l'automate si cette suite \emph{peut} conduire l'automate à un état d'acceptation. \\
 575 \end{Def}
 576
 577
 578 \begin{Ex}
 579 Dans l'exemple précédent,
 580 \begin{itemize}
 581 \item Comme $e_1$ est à la fois un état initial et d'acceptation, le mot vide fait partie du langage reconnu par l'automate.
 582 \item Le mot $aaacc$ est reconnu par l'automate.
 583 \item Les mots refusés sont ceux qui n'ont aucun chemin vers un état d'acceptation, comme $bbb$.
 584 \end{itemize}
 585 \end{Ex}
 586
 587
 588 On définit aussi de cette manière le langage $\mathcal{L}(M)$ associé à un AFND. Il est constitué de l'ensemble des mots qui, depuis l'un des états initiaux, peut conduire à l'un des états d'acceptation.
 589
 590 \begin{Exo}
 591  On considère l'automate fini $M$ non déterministe dont la relation de transition des états est donnée par la table
 592 $$\begin{array}{|c||c|c|}
 593    \hline
 594   t & 0 & 1 \\
 595  \hline
 596 e_0 & e_0, e_1 & e_1 \\
 597 e_1 & - & e_2 \\
 598 e_2 & e_2 & e_1 \\
 599 e_3 & - & e_0, e_1, e_2 \\
 600  \hline
 601   \end{array}
 602 $$
 603
 604 Si $e_0$ et $e_1$ sont les états initiaux et si $e_2$ est le seul état d'acceptation, les mots 001111 et 01001 sont-ils reconnus par $M$ ?
 605 \end{Exo}
 606
 607
 608 \noindent Réponse : 001111 est reconnu, mais pas 01001.
 609
 610
 611 \subsection{Utilité}
 612
 613 Les AFND sont beaucoup plus simple à construire que les AFD.
 614
 615 Ainsi, les algorithmes de construction automatique d'automates produisent des AFND, et les algorithmes de simplification d'automate utilisent des AFND.
 616
 617 Mais, étant non déterministes, ils ne sont pas programmables. Heureusement, on sait les déterminiser (\emph{i.e.} construire un automate de Moore qui reconnaît le même langage)...
 618
 619 \section{Détermination d'un AFND}
 620
 621 L'algorithme exposé dans ce paragraphe est appelé \emph{méthode de construction par sous-ensemble}\index{méthode de construction par sous-ensemble}. Il s'agit d'une méthode qui permet d'obtenir un automate de Moore qui reconnaît le même langage qu'un AFND.\\
 622
 623 \subsection{Méthode de construction par sous-ensemble}
 624
 625 Soit donc $M=(E,I,t,S,A)$ un AFND à états d'acceptation. Soit $Y$ une partie quelconque de $E$ et $x \in I$ une entrée quelconque.
 626
 627 \begin{Notation}
 628 On note $Y_x$ l'ensemble des états de $M$ accessibles à partir de l'un quelconque des états de $Y$ sur l'entrée $x$.
 629 \end{Notation}
 630
 631 \begin{Ex}
 632 Dans l'exemple précédent, et pour $Y = \{ e_1, e_3\}$ :
 633 \begin{itemize}
 634 \item $Y_a = \{e_1\} \cup \{ e_3 \} =  \{e_1, e_3 \}$,
 635 \item $Y_b = \{e_3\} \cup \varnothing = \{ e_3 \}$,
 636 \item $Y_c = \{e_2, e_3\} \cup \{ e_3 \} = \{e_2, e_3 \}$,
 637 \end{itemize}
 638 \end{Ex}
 639
 640
 641 On obtient un automate de Moore $\mathcal{M} = ( \mathcal{E}, \mathcal{I}, \mathcal{T}, E_0, \mathcal{A})$ de la manière suivante :
 642
 643 \begin{enumerate}
 644  \item L'ensemble $\mathcal{E}$ des états de $\mathcal{M}$ est le sous-ensemble de $\mathcal{P}(E)$ défini par :
 645 \begin{itemize}
 646 \item $S \in \mathcal{E}$,
 647 \item $\forall x \in \mathcal{I}, \forall Y \in \mathcal{E}, Y_x \in \mathcal{E}$.
 648 \end{itemize}
 649 \item L'état initial de $\mathcal{M}$ est $E_0=S$.
 650 \item L'ensemble $\mathcal{A}$ des états d'acceptation de $\mathcal{M}$ est défini par $\mathcal{A}=\{Y \in \mathcal{E} \| Y \cap A \neq \emptyset \}$.
 651 \item La fonction de transition d'états est définie par $\mathcal{T} : \mathcal{E} \times \mathcal{I} \rightarrow \mathcal{E}, (Y,x) \longmapsto \mathcal{T} (Y,x) = Y_x$.
 652 \end{enumerate}
 653
 654 \subsection{En pratique}
 655
 656 En pratique, on part de l'état initial de $\mathcal{M}$, c'est-à-dire de $S$.
 657
 658 Pour chacune des entrées, on forme l'ensemble $S_x$ des états de $M$ que la relation de transition $t$ permet d'atteindre à partir de tous les états de $S$, et on pose $\mathcal{T} (S,x) = S_x$.
 659
 660 On recommence l'opération pour chacun des états $S_x$ ainsi obtenus (pour les diverses entrées $x$), etc.
 661
 662
 663
 664 \begin{Rem}
 665 Le processus a une fin, parce que $E$ est fini, donc aussi $\mathcal{P}(E)$ : si l'automate de départ a $n$ états, l'automate déterminisé en aura au plus $2^n$..
 666 \end{Rem}
 667
 668 \begin{Rem}
 669 Il se peut qu'aucun état ne soit accessible depuis l'un quelconque des états d'un état $Y_x$ de $\mathcal{M}$, sur une entrée $y$.
 670
 671 On prend alors pour état d'arrivée de $\mathcal{M}$ l'ensemble vide ; celui-ci constitue un état particulier de $\mathcal{M}$, dont on ne peut sortir sur aucune entrée (\emph{c.f.} exemple ci-dessous).
 672 \end{Rem}
 673
 674
 675 \begin{Ex}
 676 Un exemple...\\
 677
 678 \unitlength = 0.9mm
 679 \begin{center}
 680 \begin{picture}(193,75)(0,-75)
 681 \put(0,-75){}
 682 \node[NLangle=0.0,Nmarks=i](n0)(16.0,-20.0){$e_0$}
 683
 684 \node[NLangle=0.0,iangle=128.23,Nmarks=i](n1)(44.0,-20.0){$e_1$}
 685
 686 \node[NLangle=0.0](n2)(16.0,-44.0){$e_2$}
 687
 688 \node[NLangle=0.0,Nmarks=r](n3)(44.0,-44.0){$e_3$}
 689
 690 \drawloop[ELdist=1.7,loopangle=37.45](n1){1}
 691
 692 \drawloop[ELdist=2.2,loopangle=225.0](n2){0}
 693
 694 \drawedge[ELdist=2.8](n0,n1){0}
 695
 696 \drawedge[ELdist=1.5](n1,n3){0}
 697
 698 \drawedge[ELside=r,ELdist=2.7](n2,n3){1}
 699
 700 \drawedge[ELside=r,ELdist=3.4](n0,n2){0,1}
 701
 702 \drawedge[ELside=r,ELdist=2.1](n0,n3){1}
 703
 704
 705
 706 \node[NLangle=0.0,Nw=16.0,Nmr=2.0](n40)(68.0,-32.0){$e_0$,$e_1$}
 707
 708 \node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n41)(124.0,-44.0){$e_2$,$e_3$}
 709
 710 \node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n42)(124.0,-20.0){$e_1$,$e_3$}
 711
 712 \node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n43)(96.0,-32.0){$e_1$,$e_2$,$e_3$}
 713
 714 \drawedge[ELside=r,ELdist=2.0](n40,n43){0,1}
 715
 716 \drawedge[ELdist=2.0](n43,n42){1}
 717
 718 \drawedge[ELside=r,ELdist=2.0](n43,n41){0}
 719
 720 \node[NLangle=0.0](n45)(148.0,-8.0){$e_1$}
 721
 722 \node[NLangle=0.0,Nmarks=r](n46)(148.0,-32.0){$e_3$}
 723
 724 \node[NLangle=0.0](n47)(148.0,-56.0){$e_2$}
 725
 726 \node[NLangle=0.0](n48)(168.0,-32.0){$\varnothing$}
 727
 728 \drawedge[ELdist=2.0](n42,n45){1}
 729
 730 \drawedge[ELdist=2.0](n42,n46){0}
 731
 732 \drawedge[ELside=r,ELdist=2.0](n41,n46){1}
 733
 734 \drawedge[ELside=r,ELdist=2.0](n41,n47){0}
 735
 736 \drawedge[ELdist=2.0](n47,n46){1}
 737
 738 \drawedge[ELdist=2.0](n45,n46){0}
 739
 740 \drawedge[ELdist=2.0](n46,n48){0,1}
 741
 742 \drawloop[ELdist=2.0,loopangle=0.0](n45){1}
 743
 744 \drawloop[ELdist=2.0,loopangle=0.0](n47){0}
 745
 746 \drawloop[ELdist=2.0,loopangle=0.0](n48){0,1}
 747
 748
 749
 750 \end{picture}
 751 \end{center}
 752 \end{Ex}
 753
 754
 755
 756 \begin{Exo}
 757  Construire des automates de Moore équivalents aux AFND ci-dessous :
 758 \begin{center}
 759
 760  \begin{picture}(148,67)(0,-67)
 761 \unitlength = 1mm
 762 \put(0,-67){}
 763 \node[NLangle=0.0,Nmarks=i](n4)(12.0,-19.99){3}
 764
 765 \node[NLangle=0.0,Nmarks=r](n5)(40.0,-19.99){4}
 766
 767 \node[NLangle=0.0,Nmarks=i](n6)(12.0,-44.0){0}
 768
 769 \node[NLangle=0.0](n7)(40.0,-44.0){1}
 770
 771 \node[NLangle=0.0](n8)(68.0,-44.0){2}
 772
 773 \node[NLangle=0.0,Nmarks=i](n9)(80.0,-28.0){0}
 774
 775 \node[NLangle=0.0](n10)(96.0,-12.0){1}
 776
 777 \node[NLangle=0.0](n11)(96.0,-44.0){2}
 778
 779 \node[NLangle=0.0](n12)(104.0,-28.0){3}
 780
 781 \node[NLangle=0.0,Nmarks=r](n13)(120.0,-12.0){4}
 782
 783 \node[NLangle=0.0,iangle=0.0,Nmarks=i](n14)(136.0,-28.0){6}
 784
 785 \node[NLangle=0.0,Nmarks=r](n15)(120.0,-44.0){5}
 786
 787 \drawedge[ELdist=2.0](n4,n5){0}
 788
 789 \drawedge[ELdist=2.1](n6,n4){1}
 790
 791 \drawedge[ELside=r,ELdist=2.1](n5,n6){1}
 792
 793 \drawedge(n5,n7){1}
 794
 795 \drawedge[ELdist=1.9](n7,n8){1}
 796
 797 \drawedge[ELside=r,ELdist=2.1](n8,n5){1}
 798
 799 \drawloop[ELdist=2.1](n5){0}
 800
 801 \drawloop[ELdist=2.1,loopangle=-59.26](n8){0}
 802
 803 \drawloop[ELdist=2.1,loopangle=260.34](n7){0}
 804
 805 \drawloop[ELdist=1.5,loopangle=-74.22](n6){0,1}
 806
 807 \drawedge[ELdist=2.0](n9,n10){a}
 808
 809 \drawedge[ELside=r,ELdist=2.1](n9,n11){a}
 810
 811 \drawedge[ELdist=2.1](n9,n12){a}
 812
 813 \drawedge[ELdist=2.1](n11,n15){b}
 814
 815 \drawedge[ELdist=2.0](n10,n13){b}
 816
 817 \drawedge[ELside=r,ELdist=2.1](n12,n13){c}
 818
 819 \drawedge[ELdist=2.1](n12,n15){a}
 820
 821 \drawedge[ELdist=2.0](n14,n13){c}
 822
 823 \drawedge[ELside=r,ELdist=2.1](n14,n15){a}
 824
 825
 826
 827 \end{picture}
 828 \end{center}
 829 \end{Exo}
 830
 831
 832 \begin{Exo}
 833  Construire des automates de Moore reconnaissant les langages définis par les expressions régulières :
 834 \begin{enumerate}
 835  \item $(a|b)^* b (a|b)^*$
 836  \item $((a|b)^2)^* | ((a | b)^3)^*$
 837  \item $(a^2 | b^2)^*|(a^3|b^3)^*$
 838  \item $ba^*|ab|(a|bb)ab^*$.
 839 \end{enumerate}
 840 \end{Exo}
 841
 842 \noindent Réponses : Pour $(a|b)^* b (a|b)^*$
 843
 844 \begin{center}
 845  \unitlength = 1mm
 846
 847
 848 \begin{picture}(63,26)(0,-26)
 849 \put(0,-26){}
 850 \node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}
 851
 852 \node[NLangle=0.0,Nmarks=r](n4)(48.0,-16.0){$e_1$}
 853
 854 \drawloop(n3){a}
 855
 856 \drawloop(n4){a,b}
 857
 858 \drawedge(n3,n4){b}
 859
 860 %\drawedge(n4,n4){}
 861
 862 %\drawedge(n4,n4){}
 863 \end{picture}
 864 \end{center}
 865
 866
 867 \section{Exercices}
 868
 869 \begin{Exo}
 870 Soit $\Sigma = \{a, b\}$.
 871 \begin{enumerate}
 872 \item Fabriquer un automate qui accepte les mots de longueur pair.
 873
 874 \item Fabriquer un automate qui accepte les mots de longueur impair.
 875
 876 \item Fabriquer un automate qui accepte les mots dont la longueur est congrue à 1 modulo 4.
 877 \end{enumerate}
 878 \end{Exo}
 879
 880
 881 \subsection{Propriétés d'un automate à $n$ états}
 882 \begin{Exo}
 883 Soit un automate fini déterministe $A$ qui a $n$ états et qui n'a pas d'état inaccessible.
 884
 885 Montrer qu'il existe nécessairement un mot de longueur inférieure où égale à $n-1$ qui est accepté par $A$.
 886 \end{Exo}
 887
 888
 889 \subsection{Les palindromes}
 890
 891 \begin{Exo}[Palindrome]
 892 Soit $\Sigma$ un alphabet dont le nombre de caractères est su\-pé\-rieur ou égal à deux.
 893
 894 On appelle {\em retournement} l'application
 895 $\rho: \Sigma^* \rightarrow \Sigma^*$ telle que
 896 $\rho(\epsilon) = \epsilon$ et qui associe au mot $\sigma$ de longueur non nulle le mot $\tau$, nommé {\em retourné} de $\sigma$ défini par
 897 $\tau(k) = \sigma(n-k+1)$
 898
 899 \begin{enumerate}
 900
 901 \item Déterminer $\rho(\sigma)$ quand $\sigma = aabcdea$.
 902 D'une façon générale, comment le retournement opère-t-il sur la chaîne de caractères qui représente un mot?
 903
 904 \item Exprimer $\rho(\sigma\tau)$ en fonction de  $\rho(\sigma)$ et   $\rho(\tau)$. Que vaut $\rho(\rho(\sigma))$?
 905
 906 \item  On dit qu'un mot $\sigma$ est un {\em palindrome} si $\rho(\sigma) = \sigma$.
 907 Montrer que tout mot de la forme
 908 $\rho(\sigma)\sigma$ est un palindrome.
 909 Est-ce là tous les palindromes?
 910
 911 \item  Si le nombre d'éléments de $\Sigma$ est $n$, combien y a-t-il de palindromes de longueur $p$ dans $\Sigma^*$?
 912 \end{enumerate}
 913 \end{Exo}
 914
 915
 916
 917
 918 \begin{Exo}[Suite palindrome]
 919 Soit $\Sigma=\{a,b\}$.
 920 Construire un AFD qui accepte les palindromes de longueur 3.
 921 \end{Exo}
 922
 923
 924
 925
 926 \begin{Exo}
 927 Soit $\Sigma=\{a,b\}$.
 928 On note $L$ le langage constitué des mots dans lesquels la lettre $a$, quand elle apparaît, est toujours suivie d'au moins deux lettres $b$.
 929 \begin{enumerate}
 930 \item Quels sont les mots de $L$ de longueur inférieure ou égale  6?
 931
 932 \item Construire un AFD qui accepte $L$.
 933
 934 \item Donner une expression régulière qui décrit $L$.
 935 \end{enumerate}
 936 \end{Exo}
 937
 938 \gsaut
 939 \centerline{\x{Fin du Chapitre}}
 940