Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Importer

Bienvenue sur Scribd !

  • 82 vues

    Examen 2019 2020bis Corrige

    Transféré par

    Succès Bienvenue

    Droits d'auteur :

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

    Examen 2019 2020bis Corrige

    Transféré par

    Succès Bienvenue
    82 vues3 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
    82 vues3 pages

    Examen 2019 2020bis Corrige

    Transféré par

    Succès Bienvenue

    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 3

    Département : Informatique

    Spécialité: Informatique, Niveau : Licence 2


    Faculté des
    Examen de Théorie des Langages Mathématiques et de
    l'Informatique

    NOM : PRENOM : Groupe

    Exercice 1. ( 6 pts)

    1) Déterminer les facteurs, les préfixes et les suffixes du mot u = abaab.

    • Préfixes(u) = { ε , a, ab, aba, abaa, abaab} (0,5 pt)

    • Suffixes(u) = { ε , b, ab, aab, baab, abaab} (0,5 pt)

    • Facteures(u)= { ε , a, b, ab, ba, aa, aba, baa, aab, abaa, baab, abaab} (0,5 pt)

    2) Calculer le produit L.M pour les cas suivants :

    • L = {b, aba, bab} et M = { ε }, donc L.M = L (0,5 pt)

    • L = {b, aba, bab} et M = ∅, donc L.M = ∅ (0,5 pt)

    • L = {a,b}* et M = { aa, bb }, donc L.M = tous les mots qui se terminent par aa ou bb

    (0,5 pt)

    3) On considère l’alphabet ∑ = {a,b}, et les langages L1 et L2 suivants :

    L1 = {anbn | n ≥ 0} et L2 = {anbm | n ≥ m ≥ 0}

    Calculer :

    • L1 ∪L2 = L2 (1 pt)

    • L1 ∩ L2 = L1 (1 pt)

    • L1.L2 = { anbnapbm | n ≥ 0, p ≥ m ≥ 0} (1 pt)

    Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 1/3


    NOM : PRENOM : Groupe

    Exercice 2. (8 pts)

    Pour chacun des automates (A1) et (A2) suivants :

    1) Dire s’il est déterministe ou pas (0,75 + 0,75)


    2) Dire s’il est complet ou pas. (0,75 + 0,75)
    3) Donner le langage qu’il reconnaît (1,5 + 0,5)
    4) S’il n’est pas complet, donner l’automate complet équivalent. (1,5 + 1,5)

    0,1 0,1 (A2) a,b


    0 1
    (A1)
    1 0
    A B C a,b a,b
    2

    Déterministe ? OUI / NON Déterministe ? OUI / NON

    Complet ? OUI / NON Complet ? OUI / NON

    Langage reconnu : (il suffit de donner une des trois


    Langage reconnu : (il suffit de donner une des deux réponses suivantes)
    réponses suivantes)
    L(A2) = Tous les mots sur l’alphabet {a, b} qui dont la
    L(A1) = Tous les mots sur l’alphabet {0, 1} qui longueur est multiple de 3.
    contiennent le facteur 10.
    L(A2) = { w ∈ {0, 1}* | |w| est multiple de 3}
    L(A1) = { w10w’ | w, w’ ∈ {0, 1}*}
    L(A2) = { w ∈ {0, 1}* | |w| = 3k avec k ≥ 0}

    Automate complet équivalent : Automate complet équivalent :

    0,1 0,1 Déjà complet

    1 0
    A B C

    P
    0,1

    Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 2/3


    NOM : PRENOM : Groupe

    Exercice 2. (6 pts)

    1) Trouver un automate d’états finis ayant trois états pour le langage L1 qui contient tous les
    mots sur l’alphabet Σ = {a, b} qui se terminent par ba.

    Réponse. (3 pts)

    b
    a

    b a
    0 1 2

    2) Même question pour le langage L2 qui contient tous les mots sur l’alphabet Σ = {a, b} qui ne

    contiennent pas le facteur bbab. (l’automate demandé possède quatre états)

    Réponse. (3 pts)

    b
    a
    b b a
    0 1 2 3

    Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 3/3

    Vous aimerez peut-être aussi