Scribd Logo
Importer

Bienvenue sur Scribd !

  • 11 vues

    THL EMD 2014-15

    Transféré par

    Flutter Pro

    Droits d'auteur :

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

    THL EMD 2014-15

    Transféré par

    Flutter Pro
    11 vues1 page

    Titre original

    ThL_EMD_2014-15

    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
    11 vues1 page

    THL EMD 2014-15

    Transféré par

    Flutter Pro

    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 1

    Université Mouloud MAMMERI de Tizi-Ouzou Année universitaire : 2014/2015

    Faculté de génie électrique et informatique 2 année licence – Informatique


    ième

    Département d’informatique module : Théorie des langages

    Epreuve de Moyenne Durée


    le 03/02/2015 – Durée 1h 30mn – documents non autorisés

    EXERCICE 1 : (4,5 pts)


    Une girouette est un instrument indiquant le sens du vent. On considère qu’il y a quatre directions
    possibles : est, sud, ouest et nord. On suppose aussi que l’aiguille de la girouette, indiquant le sens,
    tourne d’un quart de cercle à la fois ; soit dans le sens des aiguilles d’une montre (sens a), soit dans le
    sens opposé (sens b). On supposera que la direction initiale indiquée par la girouette est le sud.
    Soit L = ensemble des mouvements de l’aiguille qui se terminent à la position de départ.
    1) Les mots suivants sont ils dans L ? il s’agit de : abbab, babbaa, aaabaa, bbaba. (2 pts)
    2) Caractériser le langage L. (1 pt)
    3) Trouver une grammaire régulière qui génère L. (1,5 pts)

    EXERCICE 2 : (6 pts)
    Trouver :
    1) une grammaire de type 3 pour le langage : L1 = { an.b2m / n ≥ 1, m ≥ 0 } ; (1,5 pts)
    2) une grammaire de type 2 pour : L2 = { an bm / 0 ≤ m ≤ n/2 } ; (1,5 pts)
    n
    3) une grammaire de type 1 pour : L3 = { a2 / n ≥ 0 } ; (1,5 pts)
    4) une grammaire de type 0 pour : L4 = { w ∈ {a, b, c, d}* / w = an bm ci dj et n+m = i+j }. (1,5 pts)

    EXERCICE 3 : (5 pts)
    Soit L = ensemble des mots de {0, 1}* représentants les nombres divisibles par 5 (dans le système
    de numération binaire naturel).
    1) Construire un automate d’états finis simple qui accepte L. (4 pts)
    2) Donner un automate d’états finis simple qui accepte le complémentaire de L. (1 pt)

    EXERCICE 4 : (4,5 pts)


    1) En utilisant les dérivées, vérifier si les langages suivants sont réguliers :
    1-a) L1 = { a2n.b2m+1 / n ≥ 0, m ≥ 0 } ; (1,5 pts)
    1-b) L2 = { w {a, b}* / w s’écrit comme w = u.u ; où u {a, b}* }. (1,5 pts)
    2) Montrer que toute grammaire régulière à gauche est équivalente à une grammaire régulière à droite.
    (1,5 pts)

    Bon courage !

    UMMTO / L2 informatique / Théorie des Langages / EMD Février 2015 / S. Khemliche, H.Djemai, M.S.Habet

    Vous aimerez peut-être aussi