États inaccessibles

Un automate fini peut avoir des états que l’on ne peut jamais atteindre. On les appelle des états inaccessibles. En général, on veut les supprimer, car ils compliquent l’automate pour rien.

Exemple d’états inaccessibles

Considérons cet automate :

On voit que, quoi que l’on fasse, on n’arrive jamais à l’état q₃, car aucune transition n’y mène. On dit donc que l’état q₃ est inaccessible. Une question : l’état q₃ serait-il accessible si une transition partait d’un autre état pour y aboutir ? Si l’on faisait partir un arc de l’un des états q₀, q₁, q₂, q₅, il serait accessible. Et si l’on ajoutait un autre nœud et une transition partant de lui…

…alors les deux états q₃ et q₄ seraient bien sûr inaccessibles.

Définition d’un état inaccessible

On commence par définir un état accessible. Soit un automate fini A = (Q ; Σ ; δ ; q₀ ; F). On dit qu’un état q ∈ Q est accessible s’il existe un mot w ∈ Σ^∗ tel que

$(q_{0}; w) \mapsto^{*} (q; ε) .$

Un état q ∈ Q est inaccessible s’il n’est pas accessible.

Comment supprimer les états inaccessibles

Si un automate possède déjà des états inaccessibles, il vaut mieux les supprimer. On construit ainsi un automate équivalent A′ = (Q′ ; Σ ; δ′ ; q₀ ; F′) sans états inaccessibles.

On construit pas à pas l’ensemble des états accessibles. On commence par l’ensemble S₀ = {q₀}, car l’état initial est évidemment accessible. On construit l’ensemble suivant ainsi :

$S_{i} = {r | δ (q, a) = r pour un certain q \in S_{i - 1}, a \in Σ} \cup S_{i - 1}$

En clair, l’ensemble S₀ est toujours donné ; pour obtenir S₁, on prend tous les états de S₀ et l’on regarde où mènent les transitions pour toutes les lettres de Σ. On fait la réunion de ces états avec l’ensemble initial S₀. On trouve de la même façon S₂, puis les suivants. On a évidemment S_{i − 1} ⊂ S_i.

On obtient alors l’ensemble des états accessibles ainsi :

$⋃_{i = 1}^{\infty} S_{i}$

Cela peut sembler étrange de faire la réunion d’une infinité d’ensembles S_i, mais l’automate n’a qu’un nombre fini d’états. À partir d’un certain moment, les ensembles S_j, S_{j + 1} et tous les suivants sont donc égaux, si bien que même après la réunion d’une infinité d’ensembles, on obtient un ensemble fini d’états.

Revenons à l’automate

et cherchons l’ensemble de ses états accessibles. On commence par poser l’égalité de départ

$S_{0} = {q_{0}}$

Calculons maintenant l’ensemble S₁. Il faut trouver toutes les transitions partant de l’état q₀ et ajouter leurs états d’arrivée à l’ensemble S₀. Comme q₀ → ^a q₁ et q₀ → ^bq₂, l’ensemble S₁ contiendra en plus les états q₁ et q₂ :

$S_{1} = {q_{0}; q_{1}; q_{2}}$

Construisons ensuite l’ensemble S₂. On regarde où l’on peut aller à partir des états q₀, q₁, q₂. Le seul nouvel état est q₅, que l’on atteint depuis l’état q₁ :

$S_{2} = {q_{0}; q_{1}; q_{2}; q_{5}}$

Construisons maintenant l’ensemble S₃. Peut-on atteindre un nouvel état depuis q₀, q₁, q₂, q₅ ? Non, donc l’ensemble S₃ contient les mêmes éléments que S₂ :

$S_{3} = {q_{0}; q_{1}; q_{2}; q_{5}}$

Comme S₂ = S₃, on a aussi S₃ = S₄ = S₅ = … Si l’on fait la réunion de tous les S_i, on obtient l’ensemble S₂, car aucun autre élément n’apparaît dans les ensembles suivants.

L’ensemble des états accessibles de l’automate est donc {q₀ ; q₁ ; q₂ ; q₅}. On obtient les états inaccessibles par une simple différence d’ensembles :

$Q ∖ ⋃_{i = 1}^{\infty} S_{i}$

L’ensemble des états inaccessibles de notre automate est {q₃ ; q₄}. On supprime de l’automate A tous les états inaccessibles et toutes les transitions qui contenaient un état inaccessible. C’est-à-dire que l’automate équivalent sans états inaccessibles A′ = (Q′ ; Σ ; δ′ ; q₀ ; F′) associé à l’automate A = (Q ; Σ ; δ ; q₀ ; F) se définit ainsi :

$Q^{'} = ⋃_{i = 1}^{\infty} S_{i}$
∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a)
$F^{'} = F \cap Q^{'} = F \cap ⋃_{i = 1}^{\infty} S_{i}$

Sources

Chapitres: États inaccessibles, États inutiles, Minimisation d’un automate

« Précédent: Déterminisation d’un AFN

Suivant: États inutiles »