États inutiles

Un automate fini peut avoir des états depuis lesquels il est impossible d’atteindre un état final, et qui sont donc inutiles. On les appelle des états inutiles. En général, on veut les supprimer, car ils compliquent l’automate pour rien.

Exemple d’états inutiles

Considérons cet automate fini :

On voit qu’une fois arrivé dans l’état q₄ ou q₅, on ne peut plus jamais atteindre l’un des états finals q₁ ou q₂. Ces états sont donc inutiles et on peut simplement les supprimer, ce qui donne un nouvel automate, équivalent au premier : il accepte le même langage. Après suppression des états inutiles, l’automate ressemblerait à ceci :

Il accepterait le même langage. Il arrive cependant qu’il soit utile de garder certains états inutiles, par exemple quand on construit un automate complet.

Définition d’un état inutile

Soit un automate fini A = (Q ; Σ ; δ ; q₀ ; F). On dit qu’un état q ∈ Q est inutile s’il n’existe aucun mot w ∈ Σ^∗ ni aucun état q_f ∈ F tels que

$$(q;w){\mapsto }^{\ast }(q_f;\epsilon ).$$

Comment supprimer les états inutiles

On suppose que l’automate donné A = (Q ; Σ ; δ ; q₀ ; F) n’a déjà plus d’états inaccessibles. On cherche pas à pas les états qui mènent à des états finals, puis les états qui mènent à des états qui mènent à des états finals, et ainsi de suite. On obtient ainsi l’ensemble de tous les états qui ne sont pas inutiles. Au départ, on pose S₀ = F. On construit les ensembles suivants S_i pour i ∈ ℕ^* selon la règle :

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

On peut exprimer l’ensemble de tous les états qui ne sont pas inutiles ainsi :

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Et l’ensemble des états inutiles ainsi :

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Autrement dit : si S_i = S_{i + 1}, alors l’ensemble Q ∖ S_i contient les états inutiles. Illustrons la méthode sur cet automate :

On pose d’abord S₀ = {q₁ ; q₂}. On construit ensuite l’ensemble S₁ en ajoutant à S₀ tous les états qui mènent à l’un des états de S₀. On ajoute donc les états q₀ et q₃, car une transition mène de q₀ à q₁ et une autre de q₃ à q₂. On obtient S₁ = {q₀ ; q₁ ; q₂ ; q₃}. Comme S₀ ≠ S₁, on continue.

On construit l’ensemble S₂. On cherche donc tous les états depuis lesquels on peut atteindre S₁ et qui ne sont pas encore dans S₁. Il n’y en a qu’un, q₆, depuis lequel on peut atteindre l’état q₃. On obtient S₂ = {q₀ ; q₁ ; q₂ ; q₃ ; q₆}. Comme S₁ ≠ S₂, on continue.

On construit l’ensemble S₃. Existe-t-il un nouvel état depuis lequel on peut atteindre l’un des états de S₂ ? Non : depuis q₄ et q₅, on ne peut atteindre aucun des états de S₂, et les autres états sont déjà dans S₂. On a donc S₃ = {q₀ ; q₁ ; q₂ ; q₃ ; q₆}. Comme S₂ = S₃, l’algorithme s’arrête et l’ensemble S₂ est l’ensemble des états qui ne sont pas inutiles. L’ensemble {q₄ ; q₅} est l’ensemble des états inutiles.

Formellement, on construit le nouvel automate équivalent sans états inutiles ainsi. Soit l’automate A = (Q ; Σ ; δ ; q₀ ; F) ; on construit un automate équivalent A′ = (Q′ ; Σ ; δ′ ; q₀ ; F) sans états inutiles.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) si δ(q, a) ∈ Q′, sinon δ′(q, a) n’est pas définie

Sources

• M. Sipser : Introduction to the Theory of Computation
• Aho, Sethi, Ullman : Compilers: Principles, Techniques, and Tools