6. Propriétés des états

Outre les états finaux et l'état initial, il existe d'autres catégories d'états spécifiques : les états stériles, accessibles, isolés...


Etat stérile
Etat co-accessible

Un état stérile (état mort ou <<dead state>>, <<trap state>>) e est un état pour lequel il n'est pas possible d'atteindre un état final, c'est-à-dire si : LD(e) = ∅. En théorie des graphes, ils sont aussi appelés <<noeuds puits>>.

Un état qui n'est pas stérile (ie LD(e) ≠ ∅) est dit état co-accessible.

Bien sûr, les états stériles sont à éviter lors de la construction d'un automate. De même, les noeuds non initiaux pour lesquels aucune transition n'aboutit (appelés "noeuds sources" en théorie des graphes) ne sont pas utiles, et sont donc à éviter.


Etat accessible
Etat inaccessible

Un état e est dit accessible depuis un état f pour un AFN T=(A, Q, I, F, μ) si ∃ wx ∈ A* telle que (wx,f) —*/T→ (x,e).

Un état e est dit accessible pour un AFN T=(A, Q, I, F, μ) si ∃ wx ∈ A* et i ∈ I tels que (wx, i) —*/T→ (x,e) (il existe au moins un chemin de i à e, c'est-à-dire LG(e) ≠ ∅).

Dans le cas contraire, l'état e est dit inaccessible (il n'existe pas de chemin de i ∈ I à e, c'est-à-dire LG(e) = ∅).

L'état ne faisant l'objet d'aucune transition est dit isolé et n'est, lui aussi, d'aucune utilité.


Etat isolé

Un état e est dit isolé s'il ne participe à aucune transition.

Plus généralement, tout état qui ne peut être atteint depuis l'état initial en suivant les transitions ou qui est stérile est à supprimer. Autrement dit, un état (et les transitions qui le concernent) peut être supprimé de l'automate s'il est inutile, c'est-à-dire inaccessible ou stérile.


Etat utile

Soit un AFN T=(A, Q, I, F, μ) et un état e ∈ Q :

  • e est utileI s'il est accessible ;
  • e est utileF s'il est co-accessible ;
  • e est utile si : utileI(e) ∧ utileF(e) ≡ Accessible(e) ∧ co-accessible(e). Dans le cas contraire, l'état est dit inutile.

Exercices et tests :

Exercice 6.1. Donner les propriétés des états pour les automates suivants (images issues de JFLAP) :


  1. sur l'alphabet {a,b}


  2. sur l'alphabet {a,b,c,d}


  3. sur l'alphabet {0,1,2,3,4,5,6,7,8,9}


  4. sur l'alphabet {a,b,c,d}

Solution

mercredi, 17/12/03 12:31