Présenté par: Encadré par:
Assmaa Azaroual Mr.Abdeljalil Sakat
Basma El mghari
Introduction
Concepts de Base
Algorithme de Déterminisation
Applications
Conclusion
C’est quoi la determinisation ? Objectifs de la présentation
La déterminisation est une Comprendre la
technique clé en informatique déterminisation.
théorique, permettant de Apprendre les étapes du
transformer un automate non processus.
déterministe en un automate Explorer ses applications
déterministe, simplifiant ainsi pratiques.
son analyse et son utilisation
Automate fini déterministe: Automate fini non déterministe:
Un automate où, pour chaque état et Un automate où, pour un état donné
chaque symbole de l’alphabet, il existe et un symbole d’entrée, il peut y avoir
une seule transition possible et plusieurs transitions possibles. Il peut
possède exactement un état initial. aussi inclure des transitions "vides" (𝜀).
Ses caractéristiques: Ses caractéristiques:
*Pas de transitions multiples pour un *Plusieurs transitions possibles pour un
même symbole. même symbole.
*Pas de transitions "vides" (ou epsilon- *Possibilité de transitions "vides",
transitions). permettant de passer d’un état à un
*Chaque état a un comportement autre sans lire de symbole.
*Un mot est accepté si au moins un
unique pour une entrée donnée.
chemin mène à un état final.
Les états
Etat (Q): Ensemble fini d’états dans l’automate.
Exemple:{q0,q 1,q2}
État initial (𝑞0) : L’état où l’automate commence son exécution.
États acceptants (𝐹) : Ensemble des états dans lesquels l’automate accepte un mot.
Fonction de transition (𝛿)
Définit comment l’automate passe d’un état à un autre en fonction d’un symbole
d’entrée.
Alphabet (Σ)
Ensemble fini de symboles que l’automate peut lire.
Exemple:{a,b}
Mot accepté
Une séquence de symboles est acceptée si l’automate atteint un état final après avoir
traité tous les symboles du mot.
Exemple sur AFND
États : Q={q0,q1,q2}
Alphabet : Σ={a,b} a
Transitions :
De q0:
Avec a : Aller à q1
Avec b : Aller à q2 a q1
De q1 : Rester à q1avec a
De q2 : Rester à q2 avec b q0
État initial : q0 b
b
États acceptants : F={q1,q2}
q2
Sur quoi repose la déterminisation ?
La déterminisation repose sur la méthode des sous-ensembles, qui permet de
transformer un automate fini non déterministe (AFND) en un automate fini
déterministe (AFD).
Qui a développé la méthode des sous-ensembles ?
La méthode des sous-ensembles est issue des travaux fondamentaux en informatique théorique,
principalement développés dans les années 1950-1960. Des chercheurs comme Stephen Kleene, Noam
Chomsky, et Michael Rabin ont contribué à formaliser les concepts des langages formels et des
automates.
Quel était le problème que cette méthode cherchait à résoudre ?
Analyse complexe : Les automates non déterministes (AFND) étaient difficiles à analyser, car un
symbole pouvait mener à plusieurs transitions ou inclure des ε-transitions (mots vides).
Usage limité : Les AFND ne pouvaient pas être directement utilisés pour des applications pratiques
comme la reconnaissance lexicale ou la modélisation des systèmes.
Exemple d’un ADFN :
ON va appliquer l’algorithme pour rendre cette
automate un ADF
Pourquoi c’est un ADFN ?
a q0 Transitions multiples:
Exemple : Depuis l’état q2, le symbole b mène à q3
q2 a et q4.
q1
Transitions ε :
b Exemple : Une transition existe entre q0 et q1 sans
b b
lire de symbole.
b,a Présence de mots de longueur > 1:
q3 Exemple : on passe de q1 à q4 par a b.
a
b
q4
Étape 1 :
Supprimer les mots de longueur > 1
CONTEXE ACTIONS
UN AUTOMATE NON DETERMINISTE DIVISER LES TRANSITIONS EN
PEUT AVOIR UNE TRANSITION AVEC AJOUTANT DES ÉTATS
PLUS D’UN SYMBOLE ETRE DEUX SUPPLÉMENTAIRES EN FONCTION
ÉTATS DES SYMBOLES DANS LES
TRANSITIONS DE DÉPART.
EXEMPLE : DEPUIS L’ÉTAT 1, LES EXEMPLE : AJOUTER UNE ÉTAT Q5
SYMBOLE A B MÈNE VERS Q4. ENTRE Q1 ET Q4
a q0
q2 a
q1
b
b b
b,a
q3
a
b
q4
a
q0 a q0
q2 a
q2 a
q1 q1
Etape 1
b b
b b b b b
b,a q5
q3 q3
a a
a
b b
q4 q4
Étape 2 :
Gérer les ε-transitions (mots vides)
CONTEXE ACTIONS
LES Ε-TRANSITIONS PERMETTENT DE CHAQUE ÉTAT ASSOCIÉ À UNE
PASSER D’UN ÉTAT À UN AUTRE AUTRE AVEC UNE TRANSITION VIDE
SANS LIRE DE SYMBOLE. EST TRANSFORMÉ .
EXEMPLE : TRANSITION ENTRE Q0 ET EXEMPLE : Q0 --Ε--> Q1, ALORS
Q1 {Q0} DEVIENT {Q0, Q1}.
Étape 3 :
Créer des transitions uniques
CONTEXE ACTIONS
POUR UN ADFN UNE ÉTAT PEUT ON PART D’UNE ÉTAT ET ON
AMENER À DES AUTRES AVEC LE ASSOCIE L’ENSEMBLE DES ÉTAT
MEME SYMBOLE . VERS LESQUELLES ILS SE DERIGE
AVEC A ET B .
RÉPÈTE JUSQU'À CE QUE TOUS
EXEMPLE : Q2 ->{Q3,Q4} AVEC B LES ÉTATS SOIENT EXPLORÉS ET
QUE TOUTES LES TRANSITIONS
SOIENT DÉFINIES.
de la meme façon on traite q2
On part de l’état d’entrée q0.q1 et on si on trouve une transition qui ne va vers on passe à {q3,q5}
associe l’ensemble des états vers rien on crée une état poubelle . une état accepteur reste
lesquelles il se dérige avec a et b . si une état contient une état accepteur toujours accepteur
ielle devient état accepteur elle-meme
q0.q1 q0.q1
q0.q1 a b a b
a b
q2 q2
q3,q5 q3,q5
q2 b a a b
q3,q5 a
b
q3,q4 qpblle qpblle q3,q4
a,b a,b q4
a b
a b a b
q0 q2 -
q1 q2 q3,q5 q2 - q3,q4 q3 q3 q4
a q0
q2 a q5 q4 -
q1
b
b b b
q5
q3
a
a
b
q4
q0.q1 q0.q1
q0.q1
a b
a b a b
q2
q2 q2 q3,q5
q3,q5 q3,q5
a b
a b a b a
a a b
b b
qpblle q3,q4
qpblle qpblle b
q3,q4 b q3,q4 b q4
a,b a
a,b a q4 q4
a,b a
q3 b
q3 q3 b
a a,b
a
a b
a b a b
q3 q3 q4
q3 q3 q4 q4 - -
q4 - -
a q0
q2 a
q1
b
b b b
q5
q3
a
a
b
q4
il n’a plus d’état à traiter , on a obtenu un automate fini deterministe équivalent à l’automate de départ
q0.q1
a b
a q0
q2
q2 a q3,q5
q1 a b
a
b
b
b b Etape 3
qpblle q3,q4 b
a,b a q4
b,a
q3 a
b q3 b
a
q4
a,b
a
Il ne nous reste qu'à effectuer une petite vérification pour s'assurer que les mots reconnus par l'automate de
départ sont également reconnus par l'automate obtenu.
Exemple : “ab“,“abaab”,”abaab”.
Nous devons également vérifier que les mots non acceptés par l'automate de départ ne le sont pas non plus par
l'automate obtenu.
Exemple : “a”, “b”.
Déterminisons cette automate
a
3
1
b
b
b
a
2
4 a
b
a
a a
3 1,3
1 1
b b
b
aprés déterminisation b
b
a a
2 2 b
4 a 1,3,4 a
b
b
a
1,4
Cette méthode trouve des applications dans divers domaines :
CONCEPTION RECONNAISSANCE DE OPTIMISATION DES
D'ALGORITHMES MOTIFS REQUÊTES
Employés dans la planification en Utilisés dans les compilateurs, Aident à explorer plusieurs
intelligence artificielle (IA) et les moteurs de recherche et logiciels chemins pour exécuter des
graphes pour modéliser des de traitement du langage, les requêtes, réduisant le temps de
structures dynamiques. AFND permettent de reconnaître recherche dans les grandes
des structures syntaxiques dans bases de données
les langages.
Cette méthode trouve des applications dans divers domaines :
TRAITEMENT DU
BIOLOGIE INFORMATIQUE CYBERSÉCURITÉ CRYPTOGRAPHIE
LANGAGE NATUREL
Réduisent l’ambiguïté en Modélisent des systèmes Simulent plusieurs scénarios Analysent les étapes de
identifiant les structures biologiques incertains, comme pour identifier des cryptage et de décryptage
syntaxiques dans les phrases les changements dans les vulnérabilités dans les pour évaluer l’efficacité
cellules. protocoles de sécurité des systèmes.
À travers cette présentation, nous avons vu comment transformer un problème
complexe en une solution structurée grâce à un processus clair et méthodique.
En progressant étape par étape, nous avons exploré les bases théoriques, les
applications pratiques, et l’algorithme clé qui rend cette transformation possible.
Cette méthode, bien qu’abstraite, trouve des applications concrètes dans de
nombreux domaines, soulignant son importance dans la théorie et la pratique
informatique.
Pour nous contacter:
[email protected]
[email protected]
