Scribd Logo
Importer

Bienvenue sur Scribd !

  • 173 vues

    TP 3

    Transféré par

    Algérien Tout Court

    Droits d'auteur :

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

    TP 3

    Transféré par

    Algérien Tout Court
    173 vues4 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
    173 vues4 pages

    TP 3

    Transféré par

    Algérien Tout Court

    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
    Vous êtes sur la page 1sur 4

    Université Aboubekr BELKAID

    –
    Faculté des Sciences

    Département d’informatique

    Module : Compilation Année universitaire 2021-2022


    Classe : L3- Informatique
    Réalisé par : Mr MERZOUG Mohamed
    Mr ETCHIALI Abdelhak
    TP N° 03
    AUTOMATES ET EXPRESSIONS REGULIERES
    Exemples Automate :
    Soit X ={0,1,2,....,9} un alphabet et L un langage qui est l'ensemble des nombres multiples de 5
    (L={0,5,10,...etc}).
    Expression régulière :
    r : :=( (1|2|3|4|6|7|8|9)*(0|5) )+

    1
    Implémentation :
    #define Q0 0
    #define Q1 1
    int AEF_Multiple_5(char* nbr){
    int i, n=strlen(nbr);
    int etat_automate=0, etat_finale=1;
    // parcourir la chaine de caractères
    for(i=0; (i<n) && (nbr[i]!='\0'); i++)
    switch(etat_automate){
    // si le chiffre courant == 0 ou 5 le nombre devient multiple de 5
    case Q0: if(nbr[i]=='0'||nbr[i]=='5')
    etat_automate=1;
    // sinon le nombre n'est pas un multiple de 5 (a cet étape)
    else if(isdigit(nbr[i]))
    etat_automate= 0;
    // si le caractère n'est pas un chiffre, ce n'est pas un nombre et ce n'est pas multiple de 5
    else
    return 0;
    break;
    // si le chiffre courant == 0 ou 5 le nombre reste multiple de 5
    case Q1: if(nbr[i]=='0'||nbr[i]=='5')
    etat_automate=1;
    // sinon le nombre n'est pas un multiple de 5
    else if(isdigit(nbr[i]))
    etat_automate= 0;
    // si le caractère n'est pas un chiffre, ce n'est pas un nombre et ce n'est pas multiple de 5 (a cet étape)
    else
    return 0;
    break; }
    // teste si l'état courant après le parcours de la chaine de caractère est un état final (Q1 est l'état final)
    return (etat_automate==Q1);
    }

    2
    Exercice 1 :
    Soient les langages suivants :

    L1= { a*b+ }
    L2= { anbm / n est pair et m est impair }
    L3 = {a*(c+b)e+}

    1- Donnez les AEFD (automates à états finis déterministes) qui reconnaissent les langages
    précédents.
    2- Implémentez les AEFD qui correspondent aux langages L1, L2 et L3.
    Exercice 2 :
    1. Soit X={0,1} un alphabet et L1 le langage formé des suites binaires qui se terminent par la
    séquence 110.
    ( L1= {110,1110, 10110, 11110, ....etc )
    2. Soit X={a,b,c,...,z,0...9 /,<,>} un alphabet et L2 l'ensemble des balises XML ( ouvrantes, fermantes
    et vide).
    3. Soit X={0,1,2,....,9,+,-,*,/} un alphabet et L3 le langage des formules arithmétiques.
    (les opérandes ne sont pas signés).
    4. Soit X ={0,1,2,....,9} un alphabet et L4 un langage qui reconnait les nombres pairs.
    (L4={0,2,4,6,8, ……...etc})
    5. Soit X={a,b,c,..z,0…9,/,\,*,,, ;, :, !;?} un alphabet et L5 est le langage qui reconnait les
    commentaires multilignes dans le langage C. (exemple : /* 00commentaire * ;! */
    Questions :
    1- Donnez les AEFD (automates à états finis déterministes) qui reconnaissent les chaînes de L1, L2, L3,
    L4 et L5.
    2- Donnez l'expression régulière qui définit chaque langage.
    3- Traduire chaque AEFD (L1, L2, L3, L4) en un programme.
    4- en utilisant l’automate des nombres pairs, afficher les nombres pairs et impairs compris entre 20 et
    55.

    3
    Exercice supplémentaire :
    - Définissez l’alphabet, le langage et l’expression régulière qui permet de reconnaitre une adresse IP
    version IPv4.
    - Les adresses IP sont codées sur 4 octets dont la forme est la suivante :
    octet1.octet2.octet3.octet4
    - Chaque octet prend les valeurs entre 0 et 255.

    Vous aimerez peut-être aussi