Plan

• Plan
– Généralités sur les langages
– Langages régulières, expressions régulières et
automates
• Opérations sur les automates
– Surprission des 𝜀 −transitions
– Détermination d’un 𝑁𝐹𝐴
– Minimisation d’un 𝐷𝐹𝐴
– Grammaires et langages hors-contextes
Automate déterministe
Soit 𝒜 = 𝑄, 𝐴, 𝛿, 𝑞0 , 𝐹
• 𝒜 est un automate déterministe si et seulement si:
– L’automate possède un et un seul état initial 𝑞0
– Pour chaque état 𝑞 ∈ 𝑄 et pour chaque lettre de
l’alphabet 𝑎 ∈ 𝐴, il existe au plus une transition sortante
de 𝑞 étiquettée 𝑎
• Exemples:

𝑎 1 𝑎 1 𝑎 1
𝑎 𝑎 𝑎

0 𝑎 2 𝑏 0 𝑏 2
0 2

𝑏 𝑏 𝑏
Déterminisation d’un 𝑁𝐹𝐴
• L’idée de l’algorithme de déterminisation d’un
automate fini 𝒜 est de regrouper les états
accessibles par une même lettre de l’alphabet
depuis un état
– Nous considérons donc les états de notre automate
comme des ensembles d’états
– Nous commencerons par regrouper les états initiaux,
puis nous ajouterons au nouvel ensemble d’état 𝑄𝑑
les ensembles d’états accessibles depuis les états
initiaux, et ainsi de suite 𝑎 1

𝒂 𝒂

0 3

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Soit 𝒜 = 𝑄, 𝐴, 𝛿, 𝑞0 , 𝐹 un 𝑁𝐹𝐴. La construction du 𝐷𝐹𝐴 ∶ 𝒜𝑑 =
𝑄𝑑 , 𝐴, 𝛿𝑑 , 𝑞𝑑0 , 𝐹𝑑 reconnaissant le même langage que 𝒜 est
comme suit :
• 𝑄𝑑 = 2𝑄 : est constitué de tous les sous-ensembles de 𝑄
• Les alphabets de 𝒜 et de 𝒜𝑑 sont identiques: 𝐴
• 𝛿𝑑 : 𝑄𝑑 × 𝐴 ⟶ 𝑄𝑑 :
𝛿𝑑 𝑃, 𝑎 = {𝑞′ ∈ 𝑄|𝑞′ ∈ 𝛿 𝑞, 𝑎 𝑎𝑣𝑒𝑐 𝑞 ∈ 𝑃}
𝛿𝑑 𝑃, 𝑎 = ራ 𝛿 𝑞, 𝑎
𝑞∈𝑃
• 𝑞𝑑0 = {𝑞0 } ne contient qu’un état qui est l’ensemble des états
initiaux de 𝒜
• 𝐹𝑑 = 𝑃 ∈ 𝑄𝑑 𝑃 ∩ 𝐹 ≠ ∅} : toute partie de 𝑄 qui contient au
moins un état d’acceptation de 𝒜
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
Soit 𝒜 = 𝑄, 𝐴, 𝛿, 𝑞0 , 𝐹
1. Définir un tableau à deux dimensions ayant une colonne de plus que
de lettres dans l’alphabet
2. Étiqueter la première colonne “états” : les valeurs dans cette
colonne qui seront les états de l’automate déterministe
3. Étiqueter les autres colonnes par les lettres de l’alphabet
4. Placer sur une première ligne en première colonne, l’ensemble des
états initiaux de 𝒜
5. Tant qu’au moins une case du tableau n’est pas remplie :
a. choisir une case à remplir : notons 𝑃 l’ensemble d’états de 𝒜 figurant en
première colonne de la ligne de cette case, et notons 𝑎 la lettre étiquetant
la colonne de la case
b. calculer la valeur de la case : 𝛿𝑑 𝑃, 𝑎
c. si aucune ligne n’est associée à cette valeur, commencer une nouvelle
ligne étiquetée par cette valeur
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
1. Définir un tableau à deux dimensions ayant une
colonne de plus que de lettres dans l’alphabet

𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
2. Étiqueter la première colonne “états”

États

𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
3. Étiqueter les autres colonnes par les lettres de
l’alphabet
États 𝒂 𝒃

𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
4. Placer sur une première ligne en première colonne,
l’ensemble des états de départ
États 𝒂 𝒃
𝟎
𝑎

𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
5. Tant qu’au moins une case du tableau n’est pas remplie :
choisir une case à remplir et calculer sa valeur 𝛿𝑑 𝑃, 𝑎
si aucune ligne n’est associée à cette valeur, commencer une
nouvelle ligne étiquetée par cette valeur
États 𝒂 𝒃
𝟎 {𝟎, 𝟏}
𝑎

𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
5. Tant qu’au moins une case du tableau n’est pas remplie :
choisir une case à remplir et calculer sa valeur 𝛿𝑑 𝑃, 𝑎
si aucune ligne n’est associée à cette valeur, commencer une
nouvelle ligne étiquetée par cette valeur
États 𝒂 𝒃
𝟎 {𝟎, 𝟏}
𝑎
{𝟎, 𝟏}
𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
5. Tant qu’au moins une case du tableau n’est pas remplie :
choisir une case à remplir et calculer sa valeur 𝛿𝑑 𝑃, 𝑎
si aucune ligne n’est associée à cette valeur, commencer une
nouvelle ligne étiquetée par cette valeur
États 𝒂 𝒃
𝟎 {𝟎, 𝟏} 𝟎
𝑎
{𝟎, 𝟏}
𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
5. Tant qu’au moins une case du tableau n’est pas remplie :
choisir une case à remplir et calculer sa valeur 𝛿𝑑 𝑃, 𝑎
si aucune ligne n’est associée à cette valeur, commencer une
nouvelle ligne étiquetée par cette valeur
États 𝒂 𝒃
𝟎 {𝟎, 𝟏} 𝟎
𝑎
{𝟎, 𝟏} {𝟎, 𝟏}
𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
5. Tant qu’au moins une case du tableau n’est pas remplie :
choisir une case à remplir et calculer sa valeur 𝛿𝑑 𝑃, 𝑎
si aucune ligne n’est associée à cette valeur, commencer une
nouvelle ligne étiquetée par cette valeur
États 𝒂 𝒃
𝟎 {𝟎, 𝟏} 𝟎
𝑎
{𝟎, 𝟏} {𝟎, 𝟏} 𝟎
𝑎
0 1
La table de transitions ??

𝑏
Déterminisation d’un 𝑁𝐹𝐴
Calcul de l’automate déterministe complet
Soit 𝒜 = 𝑄, 𝐴, 𝛿, 𝑞0 , 𝐹 𝑁𝐹𝐴 et 𝒜𝑑 =
𝑄𝑑 , 𝐴, 𝛿𝑑 , 𝑞𝑑0 , 𝐹𝑑 le DFA correspondant
1. Appliquer l’algorithme précédent de construction de
la table de transitions
– à la fin de cet algorithme, sont connus :
• l’alphabet de 𝒜𝑑 (c’est 𝐴)
• les états de 𝒜𝑑 (ce sont les états qui apparaissent dans la
première colonne de la table)
• les transitions de 𝒜𝑑 (elles se lisent dans la table)
2. Marquer l’état initial de 𝒜𝑑 : il s’agit de l’état sur la
première ligne de la table
3. Déterminer et marquer les états terminaux de 𝒜𝑑
Déterminisation d’un 𝑁𝐹𝐴
Construction de la table de transitions
• Exemple:
États 𝒂 𝒃
→𝟎 {𝟎, 𝟏} 𝟎
𝑎
{𝟎, 𝟏} → {𝟎, 𝟏} 𝟎
𝑎
0 1
La table de transitions

𝑏 𝑏 𝑎

𝑎
0 0,1

DFA ??
Déterminisation d’un 𝑁𝐹𝐴
• Exemple
États 𝒂 𝒃
𝑏
𝑎 1 → {𝟎, 𝟐} → {𝟎, 𝟏} ∅
{𝟎, 𝟏} {𝟏} {𝟎, 𝟐}
𝑏 𝑎 𝟏 ∅ {𝟎, 𝟐}
0 2

La table de transitions
𝑎

𝑎 1
𝑎
États 𝒂 𝒃
→𝟎→ 𝟏 ∅
0 𝑏 2 𝟏 𝟐 𝟎
𝟐 ∅ 𝟎
𝑏
𝑫𝑭𝑨
On renumérote les états
Quelques propriétés
• Un automate fini déterministe est un 𝑁𝐹𝐴 non-
déterministe
– tout langage reconnu par un automate fini
déterministe est reconnu par un automate fini non-
déterministe
• Théorème de Rabin-Scott
– Les langages reconnus par les automates finis
déterministes sont exactement ceux reconnus par les
automates finis non-déterministes
Déterminisation d’un 𝑁𝐹𝐴
• Exercices :
États 𝒂 𝒃
→𝟎 {𝟎, 𝟏} 𝟎
𝑎 𝑎, 𝑏
1 {𝟎, 𝟏} {𝟎, 𝟏, 𝟐} {𝟎, 𝟐}
0 {𝟎, 𝟏, 𝟐} {𝟎, 𝟏, 𝟐, 𝟑} {𝟎, 𝟐, 𝟑}
{𝟎, 𝟐} {𝟎, 𝟏, 𝟑} {𝟎, 𝟑}
2
𝑎, 𝑏 {𝟎, 𝟏, 𝟐, 𝟑} → {𝟎, 𝟏, 𝟐, 𝟑} {𝟎, 𝟐, 𝟑}
{𝟎, 𝟐, 𝟑} → {𝟎, 𝟏, 𝟑} {𝟎, 𝟑}
𝑎, 𝑏
3 {𝟎, 𝟏, 𝟑} → {𝟎, 𝟏, 𝟐} {𝟎, 𝟐}
{𝟎, 𝟑} → {𝟎, 𝟏} 𝟎

La table de transitions
Déterminisation d’un 𝑁𝐹𝐴
• Exercices :
États 𝒂 𝒃
États 𝒂 𝒃
→𝟎 {𝟎, 𝟏} 𝟎
→𝟎 𝟏 𝟎
{𝟎, 𝟏} {𝟎, 𝟏, 𝟐} {𝟎, 𝟐}
𝟏 𝟐 𝟑
{𝟎, 𝟏, 𝟐} {𝟎, 𝟏, 𝟐, 𝟑} {𝟎, 𝟐, 𝟑}
𝟐 𝟒 𝟓
{𝟎, 𝟐} {𝟎, 𝟏, 𝟑} {𝟎, 𝟑}
𝟑 𝟔 𝟕
{𝟎, 𝟏, 𝟐, 𝟑} → {𝟎, 𝟏, 𝟐, 𝟑} {𝟎, 𝟐, 𝟑}
𝟒→ 𝟒 𝟓
{𝟎, 𝟐, 𝟑} → {𝟎, 𝟏, 𝟑} {𝟎, 𝟑}
𝟓→ 𝟔 𝟕
{𝟎, 𝟏, 𝟑} → {𝟎, 𝟏, 𝟐} {𝟎, 𝟐}
𝟔→ 𝟐 𝟑
{𝟎, 𝟑} → {𝟎, 𝟏} 𝟎
𝟕→ 𝟏 𝟎
On renumérote les états La table de transitions
Déterminisation d’un 𝑁𝐹𝐴
𝑎
• Exercices : 𝑏
𝑎 𝑎 𝑎

États 𝒂 𝒃 0 4
1 2

→𝟎 𝟏 𝟎
𝟏 𝟐 𝟑 𝑏 𝑎 𝑏 𝑏
𝟐 𝟒 𝟓 5
𝟑 𝟔 𝟕 3
𝑎 𝑎
𝟒→ 𝟒 𝟓 𝑏 𝑏
𝟓→ 𝟔 𝟕
6
𝟔→ 𝟐 𝟑
𝑎 𝑏
𝟕→ 𝟏 𝟎 𝑏
7
On renumérote les états

𝑫𝑭𝑨
Déterminisation d’un 𝑁𝐹𝐴
• Exercices :
𝑖 𝑛 𝑖
1 2 3 4

5 𝑖 6 𝑛 7 𝑖 8 𝑠 9
𝑓

0 𝑓
𝑖 𝑛 𝑖 𝑒
10 11 12 13 14

𝑓
𝑖 𝑛 𝑖 𝑒 𝑠
15 16 17 18 19 20
Déterminisation d’un 𝑁𝐹𝐴
• Exercices :
𝑠 {3,7,12,17}
{14,19}
𝑒

𝑓 𝑖 𝑛 𝑖
0 {1,5,10,15} {2,6,11,16} {3,7,12,17} {4,8,13,18}

9
Projet!!
L'objectif de ce projet est de réaliser un programme
permettant de :
• Lire un fichier .dot décrivant un automate fini
(𝑁𝐹𝐴, 𝐷𝐹𝐴, 𝜀 − 𝑁𝐹𝐴)
• implémenter :
– les fonctions élémentaires de manipulation des
automates
– les algorithmes de minimisation d’un automate :
• Suppression des 𝜀 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠
• Détermination
• Minimisation
Projet !!
Quelques étapes à suivre
• Partie 1 (pour lundi 2 mars 2020)
– Proposer les structures de données permettant l’implémentation
d’un automate
– Fonction initialisation d’un automate : permettant de lire le fichier
.dot et représenter l’automate en mémoire
– Fonction afficher l’automate : permettant
• L’affichage sur l’écran de l’automate
• Création d’un fichier .dot, génération et la visualisation du fichier png
contenant l’automate associé
• Partie 2 (pour lundi 9 mars 2020)
– Fonction de suppression des 𝜀 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛
– Fonction de déterminisation
• Partie 3 (pour lundi 23 mars 2020)
– Fonction de minimisation
• Vous pouvez ajouter toutes les fonctions que vous jugez
nécessaires !