Une transition spontanée, et sa clôture

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

Énoncé

Soit l'automate non déterministe sur ${a, b}$ d'états ${0, 1, 2}$ , initial $0$ , acceptant $1$ , avec

$0 a 0, 0 ε 1, 1 a 2, 2 b 1.$

Quel langage reconnaît-il ?
Le déterminiser. Combien d'états obtient-on ?

Corrigé

1. Depuis $0$ on lit autant de a qu'on veut, puis la transition spontanée mène en $1$ , d'où l'on parcourt le cycle $1 \to 2 \to 1$ en lisant ab. Le langage est donc $a^{*} (ab)^{*}$ .

2. La déterminisation commence par la clôture de l'état initial : ${0}$ close vaut ${0, 1}$ , car la transition spontanée s'y ajoute. On applique ensuite $Δ (S, x) = ⋃_{q \in S} δ (q, x)$ , close à son tour :

$S$	sur `a`	sur `b`
${0, 1}$	${0, 1, 2}$	$\emptyset$	initial, acceptant
${0, 1, 2}$	${0, 1, 2}$	${1}$	acceptant
${1}$	${2}$	$\emptyset$	acceptant
${2}$	$\emptyset$	${1}$
$\emptyset$	$\emptyset$	$\emptyset$	le puits

On obtient cinq états, dont le puits $\emptyset$ . Un ensemble est acceptant dès qu'il rencontre ${1}$ .

Deux remarques de méthode. La clôture de ${0}$ vaut ${0, 1}$ avant toute lecture : c'est ce que veut dire « éliminer les transitions spontanées revient à un calcul d'accessibilité ». Et le puits $\emptyset$ apparaît tout seul : la construction par sous-ensembles rend toujours un automate complet, ce qui est précisément ce qui manquait à l'automate de l'exercice précédent.

L'automate déterminisé a été comparé à l'expression $a^{*} (ab)^{*}$ sur les $2047$ mots de longueur au plus $10$ : accord complet. Il est déjà minimal — ses cinq états sont deux à deux distinguables.

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.