Une transition spontanée, et sa clôture

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.

Énoncé

Corrigé

Exercices semblables