Automates

Exercice 5.7

Déterminiser l’automate suivant : Figure 5.30

Exercice 5.8

Construire des automates déterministes qui reconnaissent les langages suivants. En déduire des automates déterministes qui reconnaissent les complémentaires de ces langages : • (a) L’ensemble des mots sur l’alphabet {0, 1} qui contiennent exactement trois fois le symbole 1. • (b) L’ensemble des mots sur l’alphabet {0, 1} qui contiennent au moins un 1.

Exercice 5.9

Construire un automate fini reconnaissant l’ensemble des mots sur l’alphabet A = {a,b} qui ne se terminent pas par abaab. Le déterminiser et minimiser.

Exercice 5.10

Montrer que les automates déterministes calculés à l’exercice 6 sont tous minimaux sauf un. Lequel ?

Exercice 5.11

Déterminiser et minimiser les automates suivants : • a) Figure 5.31 • b) Figure 5.32 190 Corrigés des exercices

Exercice 5.12

On définit la famille d’automates suivants : Aen = (Qn, I, T , E), n > 1 avec : • A = {a, b} • Qn = {0,1,…, n − 1} • I = T = {0} • Comme flèches étiquetées par a l’ensemble de (q.a.((q + 1)mod n)) pour ∀q : 0 6 q 6 n − 1 • Comme flèches étiquetées par b l’ensemble de (q.b.0) et (q.b.q) pour ∀q : 1 6 q 6 n − 1 (attention : la première inégalité commence par 0, et la seconde, par 1) Dessiner fA3 et fA4. Puis montrer que le déterminisé complet de fAn a toujours 2n états. Corrigés des exercices Exercice 5.1 Figure 5.33 Cet automate est déterministe.

Exercice 5.2

Solution (a) L’automate le plus simple qui reconnaît l’ensemble des mots sur l’alphabet {0, 1} dont l’avant  dernier symbole est 0, est le suivant : Dunod – La photocopie non autorisée est un délit 191 Chapitre 5 • Automates Figure 5.34 Cet automate n’est pas déterministe. Solution (b) L’automate le plus simple qui reconnaît l’ensemble des mots sur l’alphabet {0, 1} qui commencent et qui finissent par 0, est le suivant : Figure 5.35 Cet automate n’est pas déterministe. Solution (c) Un des nombreux automates équivalents qui reconnaissent l’ensemble des mots sur l’alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −, .} représentant en C les constantes numériques, est le suivant : Figure 5.36 Cet automate est déterministe. Solution (d) Un des nombreux automates équivalents qui reconnaît l’ensemble des mots sur l’alphabet {0, 1} comportant au moins une fois le motif 10 et au moins une fois le motif 01, est le suivant : 192 Corrigés des exercices Figure 5.37 Cet automate est déterministe. Solution (e) Un des nombreux automates équivalents qui reconnaît le langage {a nb m|n + m pair}, est le suivant : Figure 5.38 Cet automate est déterministe.

Exercice 5.3

Ajout d’un 0 à la fin d’un nombre binaire le multiplie par 2. Ajout d’un 0 à la fin d’un nombre binaire le multiplie par 2 et lui ajoute 1. Tableau 5.20 N N mod 5 Ajout d’un 0 à la fin de l’écriture binaire donne N’ : N’ mod 5 Ajout d’un 1 à la fin de l’écriture binaire donne N” : N” mod 5 5n 0 10n 0 10n + 1 1 5n + 1 1 10n + 2 2 10n + 3 3 5n + 2 2 10n + 4 4 10n + 5 0 5n + 3 3 10n + 6 1 10n + 7 2 5n + 4 4 10n + 8 3 10n + 9 4  Cela se traduit par l’automate suivant : Dunod – La photocopie non autorisée est un délit 193 Chapitre 5 • Automates Tableau 5.21 État En lisant 0 En lisant 1 0 0 1 1 2 3 2 4 0 3 1 2 4 3 4 Figure 5.39

Exercice 5.4

Figure 5.40 Exercice 5.5 États 2 et 3 ne mènent pas à la sortie. Ils sont donc inutiles. Le langage reconnu par cet automate est le même que le langage reconnu par : Figure 5.41 Il consiste en mots a, aba, ababa, abababa… qu’on peut écrire comme a(ba)* ou (ab)*a. 194 Corrigés des exercices

Exercice 5.6

Solution A1 • Cet automate lit tous les mots se terminant par bbb. • Il est émondé. • Déterminisation Tableau 5.22 État a b 0 0 01 01 0 012 012 0 0123 0123 0 0123 Figure 5.42 A1 Solution A2 • Cet automate lit tous les mots avec un b en 3ième position de la fin. • Il est émondé. • Déterminisation.