Probleme – L'explosion exponentielle est inévitable

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 29 — Langages réguliers et automates finis

Énoncé

Le chapitre affirme que la déterminisation peut coûter $2^{∣ Q ∣}$ états, et que « cette explosion est parfois inévitable ». On le démontre. Pour $k \geq 1$ , soit

$L_{k} = {w \in {a, b}^{*} : ∣ w ∣ \geq k et la k -i e ˋ me lettre avant la fin de w est un a} .$

Construire un automate non déterministe à $k + 1$ états reconnaissant $L_{k}$ .
Le déterminiser pour $k = 1, \dots, 7$ et mesurer le nombre d'états.
Démontrer que tout automate déterministe reconnaissant $L_{k}$ a au moins $2^{k}$ états.

Corrigé

1. L'automate non déterministe. États $0, 1, \dots, k$ ; initial $0$ ; acceptant $k$ .

$0 a, b 0, 0 a 1, i a, b i + 1 (1 \leq i < k) .$

Il « devine » l'endroit où commencent les $k$ dernières lettres, exige que ce soit un a, puis compte $k - 1$ lettres de plus. C'est le non-déterminisme employé comme il doit l'être : deviner, puis vérifier. Un mot est reconnu s'il existe un chemin acceptant, donc si la devinette peut être juste.

2. Les mesures. On applique la construction par sous-ensembles, puis on minimise.

$k$	états de l'AFN	après déterminisation	après minimisation	$2^{k}$
$1$	$2$	$2$	$2$	$2$
$2$	$3$	$4$	$4$	$4$
$3$	$4$	$8$	$8$	$8$
$4$	$5$	$16$	$16$	$16$
$5$	$6$	$32$	$32$	$32$
$6$	$7$	$64$	$64$	$64$
$7$	$8$	$128$	$128$	$128$

Chaque automate a été comparé au prédicat « la $k$ -ième lettre avant la fin est un a » sur tous les mots courts : accord complet. La minimisation ne gagne rien : la colonne « après minimisation » est identique à la précédente. Ce n'est pas un défaut de l'algorithme.

3. La borne inférieure. Soit $A$ un automate déterministe reconnaissant $L_{k}$ . Considérons les $2^{k}$ mots de longueur exactement $k$ . Montrons qu'ils mènent à $2^{k}$ états deux à deux distincts.

Soient $u \neq = v$ deux tels mots. Ils diffèrent en une position $i$ (comptée depuis la gauche, $1 \leq i \leq k$ ) ; disons $u_{i} = a$ et $v_{i} = b$ . Posons $w =$ n'importe quel mot de longueur $i - 1$ , par exemple $b^{i - 1}$ . Alors dans $u w$ , de longueur $k + i - 1$ , la $k$ -ième lettre avant la fin est $u_{i} = a$ : donc $u w \in L_{k}$ . Dans $v w$ , la même position porte $v_{i} = b$ : donc $v w \in / L_{k}$ .

Le mot $w$ distingue donc $u$ de $v$ . Si $u$ et $v$ menaient au même état $q$ , l'automate donnerait la même réponse sur $u w$ et $v w$ — contradiction. Les $2^{k}$ mots mènent à $2^{k}$ états distincts, et $A$ en a au moins autant.

Ce que la démonstration dit vraiment. Un automate déterministe qui lit $w$ doit, à tout instant, être capable de répondre pour toutes les suites possibles. Il lui faut donc retenir les $k$ dernières lettres — soit $2^{k}$ configurations. L'automate non déterministe, lui, ne retient rien : il devine. Le non-déterminisme n'est pas une mémoire, c'est un pari, et déterminiser, c'est payer comptant tous les paris à la fois.

C'est aussi la réponse à une question naturelle : puisque la déterminisation coûte cher, n'y aurait-il pas un algorithme plus fin ? Non. La borne est atteinte, et par une famille d'exemples très simples.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.