automates/OptimisationAutomatesFinis.tex

   1
   2
   3
   4 Des automates différents peuvent être associés au même langage.\\
   5
   6 L'optimisation des programmes d'analyse syntaxique (dont certains sont des réalisations concrètes d'automates finis) rend nécessaire la construction d'un automate minimal (en nombre d'états) qui reconnaissent un langage donné.\\
   7
   8 On se limitera dans ce chapitre à la simplification d'un automate de Moore (puisque la méthode de construction par sous-ensemble permet de se ramener d'un AFND à un AFD).
   9
  10 \section{Congruences d'automates}
  11
  12 Soit $(E,I,t)$ un AFD et $\mathcal{R}$ une relation d'équivalence sur $E$.
  13
  14 \subsection{Quelques rappels}
  15
  16 On rappelle que $\mathcal{R}$ est une relation binaire sur l'ensemble $E$ des états, qui a en plus les propriétés suivantes...
  17 \begin{description}
  18 \item[- réfléxivité.] Pour tout état $e \in E, ~ e \mathcal{R} e$,
  19 \item[- symétrie.] Pour tout couple d'états $(e_1, e_2) \in E^2$ : si $e_1 \mathcal{R} e_2$, alors $e_2 \mathcal{R} e_1$,
  20 \item[- transitivité.] Pour tout triplet d'états $(e_1, e_2, e_3) \in E^3$ : si $e_1 \mathcal{R} e_2$ et $e_2 \mathcal{R} e_3$, alors $e_1 \mathcal{R} e_3$.
  21 \end{description}
  22
  23 \medskip
  24
  25
  26 \begin{Exo}
  27 On considère l'automate :
  28
  29 \unitlength = 0.9mm
  30 \begin{center}
  31 \begin{picture}(143,75)(-50,-75)
  32 \put(0,-75){}
  33 \node[NLangle=0.0,Nmarks=i](n0)(16.0,-20.0){$e_0$}
  34
  35 \node[NLangle=0.0,iangle=128.23](n1)(44.0,-20.0){$e_1$}
  36
  37 \node[NLangle=0.0](n2)(16.0,-44.0){$e_2$}
  38
  39 \node[NLangle=0.0,Nmarks=r](n3)(44.0,-44.0){$e_3$}
  40
  41 \drawloop[ELdist=1.7,loopangle=37.45](n1){1}
  42
  43 \drawloop[ELdist=2.2,loopangle=225.0](n2){0}
  44
  45 \drawedge[ELdist=2.8](n0,n1){0}
  46
  47 \drawedge[ELdist=1.5](n1,n3){0}
  48
  49 \drawedge[ELside=r,ELdist=2.7](n2,n3){1}
  50
  51 \drawedge[ELside=r,ELdist=3.4](n0,n2){0,1}
  52
  53 \drawedge[ELside=r,ELdist=2.1](n0,n3){1}
  54 \end{picture}
  55 \end{center}
  56 \noindent et la relation binaire $e_i \mathcal{R} e_j$ si et seulement si $i$ et $j$ ont la même parité.
  57
  58 Montrez que $\mathcal{R}$ est bien une relation d'équivalence sur $E$.
  59 \end{Exo}
  60
  61
  62 On rappelle encore que  $t : E \times I \rightarrow E$ est la fonction de transition. Par la suite, par souci de concision, on notera $t_{x}(e)$  pour $t(e,x)$.
  63
  64 \subsection{Définition}
  65
  66 \begin{Def}[Congruence d'automates]
  67 On dit que $\mathcal{R}$ est une \emph{congruence d'automates}\index{congruence d'automates} si et seulement si
  68 $$\forall (r,s) \in E^2, \forall x \in I, (r \mathcal{R} s) \Longrightarrow (t_x(r) \mathcal{R} t_x(s))$$
  69 C'est-à-dire si toute paire d'états équivalents modulo $\mathcal{R}$ est transformée par toute entrée en une paire d'états équivalents modulo $\mathcal{R}$.
  70 \end{Def}
  71
  72
  73 \begin{Exo}
  74 La relation d'équivalence $\mathcal{R}$ de l'exercice précédent est-elle une congruence d'automates ?
  75 \end{Exo}
  76
  77 \subsection{Ensemble quotient}
  78
  79 Soit $\mathcal{R}$ une congruence d'automates sur l'AFD $(E,I,t)$.
  80
  81 \begin{Notation}
  82 On note $\tilde{E}$, l'ensemble quotient $E/\mathcal{R}$.\\
  83 \end{Notation}
  84
  85
  86
  87 \begin{Exo}
  88  Représenter le graphe de l'automate $M$ dont la table de transition des états est
  89 $$\begin{array}{|c|cc|}
  90    \hline
  91  t & a & b \\
  92  \hline
  93 e_0 & e_0 & e_4\\
  94 e_1 & e_1 & e_0 \\
  95 e_2 & e_2 & e_4 \\
  96 e_3 & e_5 & e_2 \\
  97 e_4 & e_4 & e_3 \\
  98 e_5 & e_3 & e_2 \\
  99 \hline
 100   \end{array}
 101 $$
 102
 103 Soit $\mathcal{R}$ la relation d'équivalence pour laquelle $E/ \mathcal{R} = \{ \{ e_0, e_2 \}, \{ e_1, e_3, e_5 \}, \{ e_4 \} \}.$
 104
 105 \begin{enumerate}
 106 \item Donner la table de transition d'états de l'automate-quotient.
 107 \item Représenter son graphe
 108 \end{enumerate}
 109 \end{Exo}
 110
 111
 112 \noindent Réponses :
 113
 114 $$\begin{array}{|c|c|c|}
 115 \hline
 116 E & a & b\\
 117 \hline
 118 A = \{e_0, e_2\} & \{e_0, e_2\} & \{e_4\} \\
 119 B = \{e_1, e_3, e_5 \}  & \{e_1, e_3, e_5 \} &  \{e_0, e_2\}\\
 120 C = \{e_4\} & \{e_4\} & \{e_1, e_3, e_5 \} \\
 121 \hline
 122   \end{array}
 123 $$
 124
 125 \begin{center}
 126 \unitlength=1mm
 127 \begin{picture}(74,83)(0,-83)
 128 \put(0,-83){}
 129 \node[NLangle=0.0](n7)(24.0,-36.0){C}
 130
 131 \node[NLangle=0.0](n8)(52.0,-16.0){A}
 132
 133 \node[NLangle=0.0](n9)(52.0,-56.0){B}
 134
 135 \drawedge[ELdist=2.0](n8,n7){b}
 136
 137 \drawedge[ELdist=2.0](n7,n9){b}
 138
 139 \drawedge(n9,n8){b}
 140
 141 \drawloop[ELdist=1.7,loopangle=53.62](n8){a}
 142
 143 \drawloop[ELdist=1.7,loopangle=-60.55](n9){a}
 144
 145 \drawloop[ELdist=1.7,loopangle=176.01](n7){a}
 146 \end{picture}
 147 \end{center}
 148
 149 \begin{Exo}
 150  Soit $M$ l'automate fini dont la table de transition des états est
 151
 152 $$\begin{array}{|c|cc|}
 153    \hline
 154  t & 0 & 1 \\
 155  \hline
 156 1 & 1 & 4 \\
 157 2 & 3 & 5 \\
 158 3 & 2 & 5 \\
 159 4 & 4 & 1 \\
 160 5 & 3 & 4 \\
 161 \hline
 162   \end{array}
 163 $$
 164
 165 Soit $\mathcal{R}$ la relation d'équivalence sur $E = \{1,2,3,4,5\}$ telle que $1 \mathcal{R} 4$ et $3 \mathcal{R} 2$.
 166 \begin{enumerate}
 167 \item Que vaut $E/\mathcal{R}$?
 168 \item Montrer que $\mathcal{R}$ est une congruence d'automates.
 169 \item Donner la table de transition des états de l'automate-quotient.
 170 \item Représenter son graphe.
 171 \end{enumerate}
 172 \end{Exo}
 173
 174
 175
 176 \begin{Exo}
 177  Soit $M$ l'automate fini dont le graphe est représenté par la figure\\
 178
 179 \begin{center}
 180 \unitlength = 1mm
 181  \begin{picture}(103,62)(0,-62)
 182 \put(0,-62){}
 183 \node[NLangle=0.0](n16)(16.0,-16.0){0}
 184
 185 \node[NLangle=0.0](n17)(40.0,-16.0){1}
 186
 187 \node[NLangle=0.0](n18)(40.0,-40.0){3}
 188
 189 \node[NLangle=0.0](n19)(64.0,-16.0){5}
 190
 191 \node[NLangle=0.0](n20)(64.0,-40.0){4}
 192
 193 \drawedge[ELside=r,ELdist=2.2](n17,n19){1}
 194
 195 \drawedge[ELside=r,ELdist=2.8,syo=1.0,eyo=1.0](n19,n17){ 1}
 196
 197 \node[NLangle=0.0](n22)(88.0,-16.0){2}
 198
 199 \drawedge[ELdist=2.1](n20,n19){1}
 200
 201 \drawedge[ELdist=2.1](n19,n22){O}
 202
 203 \drawedge[ELdist=2.1](n22,n20){1}
 204
 205 \drawedge[ELdist=2.1](n17,n18){0}
 206
 207 \drawedge[ELdist=2.1](n18,n16){1}
 208
 209 \drawedge[ELdist=2.1](n16,n17){1}
 210
 211 \drawloop[ELside=r,ELdist=2.1](n22){0}
 212
 213 \drawloop[ELside=r,ELdist=2.1](n16){0}
 214
 215 \drawloop[ELside=r,ELdist=2.1,loopangle=-87.44](n18){0}
 216
 217 \drawloop[ELside=r,ELdist=2.1,loopangle=-90.0](n20){0}
 218
 219
 220
 221 \end{picture}
 222 \end{center}
 223
 224 Le tableau ci-dessous figure une relation binaire $\mathcal{R}$ dans l'ensemble des états $E = \{ 0,1,2,3,4,5 \}$ :
 225
 226 $$\begin{array}{|c|cccccc|}
 227    \hline
 228   & 0 & 1 & 2 & 3 & 4 & 5 \\
 229 \hline
 230 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
 231 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
 232 2 & 0 & 0 & 1 & 1 & 0 & 0 \\
 233 3 & 0 & 0 & 1 & 1 & 0 & 0 \\
 234 4 & 1 & 0 & 0 & 0 & 1 & 0 \\
 235 5 & 0 & 1 & 0 & 0 & 0 & 1 \\
 236 \hline
 237   \end{array}
 238 $$
 239
 240 Un chiffre 1 à l'intersection de la ligne $i$ et de la colonne $j$ signifie que $i \mathcal{R} j$, et un chiffre 0 que ces deux éléments ne sont pas en relation.
 241 \begin{enumerate}
 242  \item Montrer que $\mathcal{R}$ est une relation d'équivalence sur $E$.
 243  \item Montrer que $\mathcal{R}$ est une congruence d'automates.
 244 \item Représenter le graphe de l'automate-quotient $M/\mathcal{R}$.
 245 \end{enumerate}
 246 \end{Exo}
 247
 248 \noindent Réponses :
 249
 250 $$\begin{array}{c|c|c}
 251 E & 0 & 1 \\
 252 \hline
 253 A = \{0, 4 \} & \{0, 4 \} & \{1, 5\} \\
 254 B = \{1, 5\} & \{3, 2\} & \{1, 5\} \\
 255 C = \{3, 2\} & \{3, 2\} & \{0, 4 \}\\
 256   \end{array}
 257 $$
 258
 259 \begin{center}
 260  \unitlength=1mm
 261
 262 \begin{picture}(74,83)(0,-83)
 263 \put(0,-83){}
 264 \node[NLangle=0.0](n7)(24.0,-36.0){C}
 265
 266 \node[NLangle=0.0](n8)(52.0,-16.0){A}
 267
 268 \node[NLangle=0.0](n9)(52.0,-56.0){B}
 269
 270 \drawedge[ELdist=2.0](n7,n8){1}
 271
 272 \drawedge[ELdist=2.0](n9,n7){0}
 273
 274 \drawedge(n8,n9){1}
 275
 276 \drawloop[ELdist=1.7,loopangle=53.62](n8){0}
 277
 278 \drawloop[ELdist=1.7,loopangle=-60.55](n9){1}
 279
 280 \drawloop[ELdist=1.7,loopangle=176.01](n7){0}
 281 \end{picture}
 282 \end{center}
 283
 284 \begin{Rem}
 285 On peut définir une application $\tilde{t}_x : \tilde{E} \rightarrow \tilde{E}$ par $\tilde{t}_x (\dot{e}) = \dot{[t_x(e)]}$, puis une application $\tilde{t} : \tilde{E} \times I \rightarrow \tilde{E}$ par $(\dot{e},i) \longmapsto \tilde{t}_x(\dot{e})$.
 286 \end{Rem}
 287
 288 \section{\'Equivalence de Nérode}
 289
 290 \subsection{L'équivalence}
 291
 292 Soit $M = (E,I,t,e_0,A)$ un automate de Moore, deux états $q$ et $s$ de $E$, et $w \in I^*$ un mot d'entrée.
 293
 294 \begin{Def}[w-compatibles]
 295  $q$ est $s$ sont \emph{$w$-compatible}\index{w-compatible} si et seulement si $$t_w(q) \in A \Longleftrightarrow t_w(s) \in A$$
 296 \end{Def}
 297
 298 Cette définition permet de définir une relation $\sim$ dans $E$ par
 299
 300 $$(q \sim s) \Longleftrightarrow \left(\forall w \in I^*, q \textrm{ et } s \textrm{ sont } w \textrm{-compatibles} \right)$$
 301
 302 \begin{Def}[\'Equivalence de Nérode]
 303 Cette relation est manifestement une relation d'équivalence, elle est appelée \emph{\'equivalence de N\'erode}\index{équivalence!de Nérode} associée à $M$.
 304 \end{Def}
 305
 306
 307 On démontre facilement que cette équivalence est une congruence d'automates. Tout automate de Moore peut donc être remplacé par son quotient par l'équivalence de Nérode.
 308
 309 Dans ce quotient, le nombre d'états est évidemment plus petit, l'automate obtenu est donc plus \og simple\fg{}.
 310
 311
 312
 313
 314
 315
 316 \subsection{L'algorithme}
 317
 318 \subsubsection{La théorie}
 319
 320 Pour obtenir l'équivalence de Nérode associée à un automate, on dispose de l'algorithme suivant...\\\\
 321
 322 Soit $M=\{E,I,t,e_0,A\}$ un automate de Moore.
 323
 324 On définit, pour tout $k \in \mathbb{N}$, une relation $\mathcal{R}_k$ sur E en posant
 325
 326 $$[ q \mathcal{R}_k s ] \Longleftrightarrow \left[ (\forall w \in I^*), (l(w) \leqslant k \Longrightarrow q \text{ et } s \text{ sont } w\text{-compatibles}) \right]$$
 327
 328 Donc $q$ et $s$ sont en relation par $\mathcal{R}_k$ lorsqu'ils sont $w$-compatibles, pour tout mot $w$ de longueur inférieure ou égale à $k$.\\
 329
 330 Cette relation est clairement une relation d'équivalence, et $\mathcal{R}_{k+1}$ est plus fine que $\mathcal{R}_k$. L'équivalence de Nérode est l'intersection de ces relations $\mathcal{R}_k$, pour toutes les valeurs de $k$ entier.
 331
 332 \subsubsection{La pratique}
 333
 334 Cet algorithme n'est pas utilisable dans la pratique. On fait plutôt...
 335
 336 \begin{enumerate}
 337  \item Prendre comme partition de départ $P_0 = \{A, E \setminus A \}$.
 338  \item Si $P_k=\{E_1, \hdots, E_n \} $ est la partition correspondant à la relation $\mathcal{R}_k$, morceler éventuellement chaque classe $E_i$ en sous-classes $E_{i1}, E_{i2}, \hdots, E_{ip}$ de manière que deux états $q$ et $s$ appartiennent à la même sous-classe si, pour toute entrée $x$, les états $t_x(q)$ et $t_x(s)$ appartiennent à la même classe $E_j$ (pouvant dépendre de $x$).
 339
 340 L'ensemble des sous-classes obtenues constitue la partition correspondant à la relation $\mathcal{R}_{k+1}$
 341 \item Répéter l'étape précédente jusqu'à ce que $P_{k+1}=P_k$. La relation $\mathcal{R}_k$ est alors l'équivalence de Nérode associée à M.
 342 \end{enumerate}
 343
 344 \begin{Rem}
 345 L'étape (3) est nécessairement atteinte, puisque les relations $\mathcal{R}_k$ sont de plus en plus fines.
 346
 347 Au pire, $P = \{ \{q \} \|q \in E \}$, la relation est l'égalité : ceci signifie que l'automate n'est pas simplifiable.
 348 \end{Rem}
 349
 350
 351 \begin{Ex}
 352  Un automate de Moore et l'automate simplifié.
 353 \scriptsize
 354 \begin{center}
 355 \unitlength = 0.8mm
 356 \begin{picture}(174,77)(0,-77)
 357 \put(0,-77){}
 358 \node[NLangle=0.0,Nmarks=i](n24)(12.0,-12.0){1}
 359
 360 \node[NLangle=0.0](n25)(40.0,-12.0){2}
 361
 362 \node[NLangle=0.0,Nmarks=r](n26)(68.0,-12.0){3}
 363
 364 \node[NLangle=0.0,Nmarks=r](n27)(12.0,-36.0){4}
 365
 366 \node[NLangle=0.0](n28)(68.0,-36.0){7}
 367
 368 \node[NLangle=0.0,Nmarks=r](n29)(40.0,-60.0){5}
 369
 370 \node[NLangle=0.0](n30)(68.0,-60.0){6}
 371
 372 \drawedge[ELdist=2.0](n24,n25){a}
 373
 374 \drawedge[ELside=r,ELdist=2.0](n24,n27){b}
 375
 376 \drawedge[ELdist=2.0](n27,n28){b}
 377
 378 \drawedge[ELside=r,ELdist=2.0](n25,n28){b}
 379
 380 \drawedge[ELside=r,ELdist=2.0](n26,n28){a}
 381
 382 \drawedge[ELdist=2.0](n29,n28){a}
 383
 384 \drawedge[ELdist=2.0](n30,n28){b}
 385
 386 \drawedge[ELdist=2.0](n27,n29){a}
 387
 388 \drawedge[ELside=r,ELdist=3.1,syo=1.0,eyo=1.0](n26,n25){ b}
 389
 390 \drawedge[ELside=r,ELdist=2.0](n25,n26){a}
 391
 392 \drawedge[ELdist=3.0,syo=1.0,eyo=1.0](n29,n30){ b}
 393
 394 \drawedge[ELdist=2.0](n30,n29){a}
 395
 396 \drawloop[ELdist=2.5,loopangle=1.1](n28){a,b}
 397
 398 \node[NLangle=0.0,Nmarks=i](n31)(96.0,-20.0){1}
 399
 400 \node[NLangle=0.0,Nmarks=r](n32)(96.0,-52.0){4}
 401
 402 \node[NLangle=0.0,Nmarks=r](n33)(128.0,-52.0){3,5}
 403
 404 \node[NLangle=0.0](n34)(128.0,-20.0){2,6}
 405
 406 \node[NLangle=0.0](n35)(152.0,-36.0){7}
 407
 408 \drawloop[ELdist=2.0,loopangle=0.0](n35){ a,b}
 409
 410 \drawedge[ELside=r,ELdist=2.0](n31,n32){b}
 411
 412 \drawedge[ELdist=2.0](n31,n34){a}
 413
 414 \drawedge[ELdist=2.0](n32,n33){a}
 415
 416 \drawedge[ELdist=2.0](n34,n35){b}
 417
 418 \drawedge[ELdist=2.0](n33,n35){a}
 419
 420 \drawedge[ELdist=2.0,sxo=1.0,exo=1.0](n34,n33){ a}
 421
 422 \drawedge[ELdist=2.0](n33,n34){b}
 423
 424 \drawbpedge[ELside=r,ELdist=2.0](n32,-90,19.99,n35,-89,37.16){b}
 425
 426 \end{picture}
 427 \end{center}
 428 \end{Ex}
 429
 430 \normalsize
 431
 432 \begin{Exo}
 433  On donne un AFD par la table de transition des états suivante :
 434 $$\begin{array}{|c||c|c|}
 435    \hline
 436 t & a & b\\
 437 \hline
 438 0 & 1 & 2 \\
 439 1 & 5 & 3 \\
 440 2 & 5 & 1 \\
 441 3 & 4 & 5 \\
 442 4 & 5 & 4 \\
 443 5 & 5 & 5 \\
 444 \hline
 445 \end{array}$$
 446
 447 \'Etat initial : 0
 448
 449 \'Etats d'acceptation : 4
 450
 451
 452 \noindent Cet automate reconnaît le langage défini par l'expression régulière $(a|bb)bab^*$.
 453
 454 \noindent Appliquer la méthode de l'équivalence de Nérode pour trouver l'automate minimal reconnaissant le langage.
 455 \end{Exo}
 456
 457
 458 \begin{Exo}
 459 Faire de même avec l'automate de Moore dont la table de transition est :
 460 $$\begin{array}{|c||c|c|}
 461    \hline
 462 t & a & b\\
 463 \hline
 464 a & a & c \\
 465 b & g & d \\
 466 c & f & e \\
 467 d & a & d \\
 468 e & a & d \\
 469 f & g & f \\
 470 g & g & c \\
 471 \hline
 472 \end{array}
 473 $$
 474 \end{Exo}
 475
 476
 477 \section{Méthode du dual}
 478
 479 \subsection{Dual d'un automate}
 480
 481 Soit $M = (E,I,t,S,A)$ un automate quelconque (AFD ou AFND).
 482
 483 \begin{Def}
 484 L'automate dual de $M$ est l'automate $M^{-1} = (E,I,t',A,S)$, où $t'$ est la relation sur $E$ obtenue en renversant toutes les flèches sur le graphe de $M$, c'est-à-dire si $R' \subset (E \times I) \times E$ est le graphe de la relation $t'$, alors que le graphe de $t$ est $R$, on a
 485 $$((e,i),e') \in R' \Longleftrightarrow ((e',i),e) \in R$$
 486 \end{Def}
 487
 488 Il est clair que $M$ reconnaît un mot $w \in I^*$ si et seulement si $M^{-1}$ reconnaît le mot $w^{-1}$ (si $w = a_1 a_2 \hdots a_n$, alors $w^{-1} = a_n a_{n-1} \hdots a_1$).
 489
 490 Le dual d'un automate à comportement déterminé n'est pas nécessairement à comportement déterminé.
 491
 492
 493 \subsection{Méthode du dual}
 494
 495 Soit $M$ un automate de Moore :
 496
 497 \begin{enumerate}
 498  \item Construire l'automate dual $M^{-1}$ de $M$.
 499  \item Appliquer la construction par sous-ensembles à $M^{-1}$ pour le transformer en automate $M'$ de Moore.
 500  \item Construire le dual ${M'}^{-1}$ de $M'$.
 501  \item Appliquer la construction par sous-ensemble à ${M'}^{-1}$ pour obtenir l'automate de Moore $M''$.
 502 \end{enumerate}
 503
 504 L'automate $M''$ est l'automate minimal tel que $\mathcal{L}(M'') = \mathcal{L}(M)$.
 505
 506
 507
 508 \begin{Exo}
 509  On donne un AFD par la table de transition des états suivante :
 510 $$\begin{array}{|c||c|c|}
 511    \hline
 512 t & a & b\\
 513 \hline
 514 0 & 1 & 2 \\
 515 1 & 3 & 4 \\
 516 2 & 3 & 4 \\
 517 3 & 5 & 6 \\
 518 4 & 5 & 6 \\
 519 5 & 7 & 8 \\
 520 6 & 7 & 8 \\
 521 7 & 9 & 10 \\
 522 8 & 9 & 10 \\
 523 9 & 11 & 12 \\
 524 10 & 11 & 12 \\
 525 11 & 1 & 2 \\
 526 12 & 1 & 2 \\
 527 \hline
 528   \end{array}
 529 $$
 530
 531 \'Etat initial : 0
 532
 533 \'Etats d'acceptation : 0 3 4 5 6 7 8 11 12
 534
 535
 536 \noindent Cet automate reconnaît le langage défini par l'expression régulière $((a|b)^2)^* | ((a|b)^3)^*$.
 537
 538 \noindent  Appliquer la méthode du dual pour trouver l'automate minimal reconnaissant le langage.
 539 \end{Exo}
 540
 541
 542
 543 \begin{Exo}
 544  On donne un automate non déterministe, à transitions instantannées, par la table de transition suivante :
 545 $$\begin{array}{|c||c|c|c|}
 546    \hline
 547 t & \varepsilon & a & b\\
 548 \hline
 549 0 & 1,11 &   & \\
 550 1 & 2, 7 &   & \\
 551 2 &      &   & 3 \\
 552 3 & 4, 6 &   & \\
 553 4 &      & 5 & \\
 554 5 & 4, 6 &   & \\
 555 6 & 10   &   & \\
 556 7 &      & 8 & \\
 557 8 &      &   & 9 \\
 558 9 & 10   &   & \\
 559 10 & 22  &   & \\
 560 11 & 12,14 & & \\
 561 12 &     & 13 & \\
 562 13 &     &    & \\
 563 14 & 17    &    & 15 \\
 564 15 &     &    & 16 \\
 565 16 &  17   &    & \\
 566 17 &     & 18   & \\
 567 18 & 19,21    &    & \\
 568 19 &     &    & 20 \\
 569 20 & 19,21    &    & \\
 570 21 &  22   &    & \\
 571 22 &     &    & \\
 572 \hline
 573   \end{array}
 574 $$
 575
 576 \'Etat initial : 0
 577
 578
 579 \'Etat d'acceptation : 22
 580
 581
 582
 583 \noindent Cet automate reconnaît le langage défini par l'expression régulière $ba^* | ab | (a | bb) ab^*$.
 584
 585 \noindent Le déterminiser, puis lui appliquer la méthode de votre choix pour obtenir l'automate minimal reconnaissant le langage.
 586 \end{Exo}
 587
 588
 589
 590
 591
 592
 593 \begin{Exo}
 594  On donne la table de transition suivante pour un automate fini :
 595 $$\begin{array}{|c||c|c|}
 596 \hline
 597    t & a & b \\
 598  \hline
 599 0 & 1 & 2 \\
 600 \hline
 601 1 & 3 & 4 \\
 602 \hline
 603 2 & 5 & 6 \\
 604 \hline
 605 3 & 1 & 2 \\
 606 \hline
 607 4 & 7 & 8 \\
 608 \hline
 609 5 & 7 & 8 \\
 610 \hline
 611 6 & 1 & 2 \\
 612 \hline
 613 7 & 9 & 10 \\
 614 \hline
 615 8 & 10 & 11 \\
 616 \hline
 617 9 & 7  & 8 \\
 618 \hline
 619 10 & 10 & 10 \\
 620 \hline
 621 11 & 7 & 8 \\
 622 \hline
 623   \end{array}
 624 $$
 625
 626 L'état initial est 0, et les états d'acceptation sont 4, 5, 9 et 11.\\
 627
 628 \noindent Appliquer à cet automate l'algorithme de votre choix pour obtenir l'automate minimal reconnaissant le même langage (équivalence de Nérode ou dual).
 629
 630 (L'automate minimal possède 7 états).
 631 \end{Exo}
 632
 633 \section{Synthèse}
 634
 635 \subsection{Outils}
 636
 637 \subsubsection{Construction par sous-ensemble}
 638
 639
 640 \begin{description}
 641 \item[Domaine d'application : ] Cette méthode s'applique aux automates finis non déterministes. Il est aussi possible de l'utiliser sur un AFD, mais c'est sans intérêt.
 642 \item[Résultat : ] Automate reconnaissant le même langage.
 643 \item[But : ] Obtenir un AFD reconnaissant le même langage.
 644 \item[Autre utilisation : ] Peut permettre d'obtenir l'automate minimal reconnaissant le même langage (méthode du dual).
 645 \end{description}
 646
 647 \subsubsection{\'Equivalence de Nérode}
 648
 649 \begin{description}
 650 \item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
 651 \item[Résultat : ] Le quotient de l'automate considéré par l'équivalence de Nérode ; un automate ne reconnaissant généralement pas le même langage.
 652 \item[But : ] Simplifier l'automate considéré, si c'est possible, grâce à la méthode des quotients.
 653 \end{description}
 654
 655 \subsection{Méthodes d'optimisation}
 656
 657 \subsubsection{Méthode des quotients}
 658
 659 \begin{description}
 660 \item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
 661 \item[Moyens : ] \'Equivalence de Nérode.
 662 \item[Résultat : ] On obtient l'automate minimal reconnaissant le même langage.
 663 \end{description}
 664
 665 \subsubsection{Méthode du dual}
 666
 667 \begin{description}
 668 \item[Domaine d'application : ] Cette méthode ne s'applique qu'aux automates finis dé\-ter\-mi\-nis\-tes (AFD).
 669 \item[Moyens : ] Construction par sous-ensembles.
 670 \item[Résultat : ] L'automate de Moore minimal reconnaissant le même langage.
 671 \item[Efficacité : ] \'Elégant, mais pas efficace.
 672 \end{description}
 673
 674
 675 \gsaut
 676 \centerline{\x{Fin du Chapitre}}
 677