Scribd
Importer
8 vues29 pages

Automates finis et langages réguliers

les expressions regulieres

Transféré par

gosranihamida88
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
8 vues29 pages

Automates finis et langages réguliers

les expressions regulieres

Transféré par

gosranihamida88
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Chapitre 2

Les automates finis


et les langages
réguliers
D R I N G FAT M A S O M A A

CPI2
Objectifs des automates
Les automates à états finis sont utilisés comme modèle pour :

Conception des circuits logiques


Analyse lexicale de compilateurs
La recherche de mots clés dans le Web.
Vérification des systèmes à états finis. Comme par exemple des protocoles de communications.
Exemples
Automate fini modélisant un système de On/Off

Automate fini reconnaissant la chaîne then


Motivation
Problème: est ce qu’une chaîne w appartient à un langage L?
Quels sont les ressources nécessaires pour répondre à cette question.

 Reconnaisseur d’un langage


Programme qui prend en entrée une chaîne x et répond par oui ou non. (x appartient ou
non au langage)
On peut résonner pour les problèmes non pas comme une réponse Oui /non mais comme
transformation des entrées en des sorties.
Automate à états finis
définition informelle
Protocole de e-commerce en utilisant e-money (magasin, client, banque)

Événements:
1. Le client peut payer le magasin (envoie de fichier de monnaie)
2. Le client peut annuler envoie de monnaie (comme mettre une opposition au chèque)
3. Le magasin peut envoyer la marchandise au client
4. Le magasin peut checker la monnaie
5. La banque peut transférer l’argent au magasin
Automate à états finis
définition informelle
Automate à états finis déterministe
définition formelle
Ensemble fini d’états Q
Alphabet de symboles d’entrées 
Un état initial (un élement de Q) q0
Zéro ou plus d’états d’acceptation ou finaux (sous ensemble de Q) F
Une fonction de transition 
Automate à états finis déterministe
définition formelle
Une fonction de transition 
• Arguments : état et un symbole d’entrée
• Retourne un état

• Intuitivement; si un automate fini( AF) est dans un état qi et


reçoit l’entrée a (reconnaît), alors l’AF passe à l’état qj
Automate à états finis déterministe
définition formelle
Un Automate à états Finis Déterministe (DFA)
État initial

M  Q, ,  , q0 , F 
Ensemble d’entrées
Ensemble d’états finaux
Alphabet d’entrées

Fonction de transition
Automate à états finis déterministe
définition formelle
Exemple
 a b
q0 q1 q5
  a, b
q1 q5 q2
Q  q0 , q1, q2 , q3 , q4 , q5 
q2 q5 q3
F  q4  q3 q4 q5
q4 q5 q5
q5 q5 q5
Mot accepté par un automate
Un automate Fini accepte une chaîne w = a1a2…an S’il existe un chemin dans le diagramme de
transition qui :
1. Commence à l’état initial.
2. Finie à un états d’acceptation (ou final)
3. Possède la séquence libellé par a1a2…an
Extension de la fonction de transition
Elle nous dit dans quel état on arrive en partant de l’état qi et en analysant la chaîne w

 * q, w  q
Extension de la fonction de transition
Exemple

 * q0 , abbbaa   q5
Langage accepté
Le langage L(M)contient toutes les chaînes acceptées par M

L(M) = { toutes les chaînes menant l’automate M vers un état final}


Langage rejeté
Exemples

LM   {a b : n  0}
n
Exemples
LM   {a b : n  0}
n
Exemples

LM   { toutes les chaînes avec prefixe ab}


Exemples
LM   { toutes les chaînes avec prefixe ab}
Exemples

LM   { toutes les chaînes sauf 001 }


Exemples
LM   { toutes les chaînes sauf 001 }
Exemples

LM   {w contient un nombre pair de b}


Exemples
LM   {w contient un nombre pair de b}
Exemples

LM   Tout les mots sur l’ alphabet {a, b}


Exemples
LM   Tout les mots sur l’ alphabet {a, b}
Automates finis complets
Un automate fini déterministe est complet si  et une fonction totale sur Q

De chaque état il part exactement une flèche étiqueté par chacune des lettres de l’alphabets 

Exemple
Erreurs
Ne pas confondre un automate M avec L(M). En fait M est un programme et L(M) est un
ensemble de chaînes.

L’état initial q0 est de type état tan disque F est de type ensemble d’états (représente
l’ensemble des états finaux)

 Est ce que a est un symbole ou une chaîne de longueur 1.


Ca dépend du contexte par exemple si a est utilisé comme entrée de la fonction ou *
Exercices

Voir TD
Questions ?

Vous aimerez peut-être aussi