Scribd Logo
Importer

Bienvenue sur Scribd !

  • 111 vues

    Chapitre 4 Expressions Et Automates

    Transféré par

    OUMAIMA ELMEJGARI

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Chapitre 4 Expressions Et Automates

    Transféré par

    OUMAIMA ELMEJGARI
    111 vues21 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    111 vues21 pages

    Chapitre 4 Expressions Et Automates

    Transféré par

    OUMAIMA ELMEJGARI

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 21

    Faculté des Sciences Agadir

    Département Informatique
    Filière SMI
    Semestre 5

    Compilation
    Pr. Mustapha Machkour
    Compilation
    Par M.Machkour
    Chapitre 4
    Transformation de l'expression régulière en
    automate

    Compilation FS Agadir SMI 20-21 3


    Objectifs
     Automate fini déterministe
     Automate fini non déterministe
     Transformation d'une expression régulière en
    automate fini non déterministe

    Compilation FS Agadir SMI 20-21 4


     Définition de ε-transition
    ε-transition est une transition par le symbole ε entre
    deux états.

    Compilation FS Agadir SMI 20-21 5


     Automate fini déterministe : AFD
    Un automate fini est dit déterministe s'il ne contient
    pas de
    ε-transition
    et
    si pour chaque couple
    (état , symbole) il y a au plus une
    transition étiqueté symbole partant de état.

    Compilation FS Agadir SMI 20-21 6


     Contre-exemple (AFND)

    a 1 b
    0 2

    Compilation FS Agadir SMI 20-21 7


     Contre-exemple (AFND)

    a 1 b
    0 2

    Compilation FS Agadir SMI 20-21 8


     Exemple ((a|b)*cb)

    c 1 b
    0 2

    Compilation FS Agadir SMI 20-21 9


     Exercice
    Chercher un automate pour
    (a|b)*abb

    Compilation FS Agadir SMI 20-21 10


     Passage des E.R aux automates finis
    Comment?
    On considère le schéma

    Compilation FS Agadir SMI 20-21 11


     Algorithme de passage d'une ER en AFND
    Algorithme
    Entrées : une ER r sur un alphabet A
    Sortie : un AFND N qui reconnaît L(r).
    Début
    Construire un AFND pour ε. soit

    Compilation FS Agadir SMI 20-21 12


     Algorithme de passage d'une ER en AFND
    Algorithme

    Construire pour chaque a de A

    Compilation FS Agadir SMI 20-21 13


     Algorithme de passage d'une ER en AFND
    Algorithme

    Construire pour l'expression X|Y l'automate défini par

    ε N(X) ε
    i f
    ε N(Y) ε

    Compilation FS Agadir SMI 20-21 14


    Construire pour l'expression XY l'automate défini par

    N(X) N(Y) f
    i

    Compilation FS Agadir SMI 20-21 15


    - construire pour l'expression X* l'automate défini par
    ε

    N(X) f
    i ε ε

    fin algo.

    Compilation FS Agadir SMI 20-21 16


    ou bien pour X*
    ε

    i ε N(X) f

    ε
    fin algo.

    Compilation FS Agadir SMI 20-21 17


     Exercices
    - Construire un AFND correspondant à l'ER
    X=abb.
    - Construire AFND pour l'ER a|b.
    - Chercher l’AFND de a+
    - Construire AFND pour l'ER Y=(a|b)*.
    - Construire AFND pour l'ER Z=XY.

    Compilation FS Agadir SMI 20-21 18


     Exercices
    - Construire un automate fini pour le langage binaire.
    - Chercher un automate qui décrit l'E.R. (ab|ba)*
    - Chercher un automate qui décrit l'E.R. (ab|ba)+
    - Chercher un automate pour les nombres binaires où
    chaque 1 est suivi directement de 0;

    Compilation FS Agadir SMI 20-21 19


     Travail à faire
    Suite du micro compilateur de C:
    Reconnaissance des id , des constantes numériques
    (commencer par les constantes entières) et des
    opérateurs.

    Compilation FS Agadir SMI 20-21 20


    Résumé
     Automate fini déterministe
     Automate fini non déterministe
     Transformation d'une expression régulière en
    automate fini non déterministe

    Compilation FS Agadir SMI 20-21 21

    Vous aimerez peut-être aussi