Scribd Logo
Importer

Bienvenue sur Scribd !

  • 21 vues

    THL Serie1 2015

    Transféré par

    Flutter Pro

    Droits d'auteur :

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

    THL Serie1 2015

    Transféré par

    Flutter Pro
    21 vues2 pages

    Titre original

    ThL_serie1_2015 (2)

    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
    21 vues2 pages

    THL Serie1 2015

    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 2

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

    Faculté de génie électrique et informatique 2ième année Licence-Informatique


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

    SÉRIE D’EXERCICES no 1

    EXERCICE 1 :
    Soit le mot x = ((acbc)R.baca)R (αR désigne le reflet miroir de α)
    1) Donner la chaîne de caractères à laquelle x est égal.
    2) Quelle est la valeur de |x|, |x|a, |x|b et |x|c ?
    3) Donner un préfixe propre de x contenant au moins deux lettres ‘c’.
    4) Donner un suffixe propre de x contenant une seule lettre ‘a’.

    EXERCICE 2 : Soit la grammaire G = ({a, b, c} , {S, A} , S , P)


    où P contient les règles suivantes :
    S → aS | bA ; A → cA | ε
    1) Déterminer si les mots w1 = abac, w2 = aabccc, w3 = cabbac et w4 = ab sont générés par G.
    2) Trouver le langage généré par G ( qu’on note L(G) ).

    EXERCICE 3 : Pour chacune des grammaires Gi = ({a, b, c} , {S, A, R, T} , S , Pi), (i=1,..,5) ; donner le
    type de celle-ci, puis trouver le langage engendré par chacune d’elles :
    1) P1 : S → bA ; A → aA | ε
    2) P2 : S → aSc | A
    A → bAc | ε
    3) P3 : S → aSbS | ε
    4) P4 : S → aRbc | abc
    R → aRTb | aTb ; Tb → bT ; Tc → cc
    5) P5 : S → aAb | ε
    A → aSb
    Ab → ε

    EXERCICE 4 : Pour chacun des langages suivants, donner une grammaire qui l’engendre :
    a) L1 = { 02n / n ≥ 0 } f) L6 = { am bn an bm / n ≥ 1, m ≥ 1 }
    b) L2 = { 0n 1n / n ≥ 0 } g) L7 = { w  {a, b}+ / |w| ≡ 0[3] }
    c) L3 = { an b2n / n ≥ 0 } h) L8 = { 0i 1j / i ≥ j ≥ 0 }
    d) L4 = { an bm / n ≤ m ≤ 2  n } i) L9 = { 0i 1j / i ≠ j, i ≥ 0, j ≥ 0 }
    n
    e) L5 = { 0n w wR 1n / n ≥ 0 , w  {a, b}* } j) L10 = { a2 / n ≥ 0 }

    EXERCICE 5 : Soit L un langage de type i  {0, 1, 2, 3}. Est-il possible qu’un langage L’  L
    ne soit pas de type i ?
    indication : on sait que le langage { 0n1n / n ≥ 0 } n’est pas régulier.

    Théorie des Langages – série n° 1 Page 1 sur 2 2014/2015


    EXERCICE 6 : Soit le langage L défini comme suit :
    L = { a2 n b c2 m + 1 / n, m ≥ 0 }.
    1) Montrer que L est de type 3 en trouvant une grammaire de type 3 qui l’engendre.
    2) Trouver une grammaire de type 2, et qui n’est pas de type 3, qui engendre L.

    EXERCICE 7 : Soit le langage L défini comme suit :


    L = ensemble de tous les mots de {0, 1}* qui contiennent un nombre pair de « 1 ».
    Mêmes questions, pour L, que l’exercice 6.

    EXERCICE 8 : Soit la grammaire G dont les règles de production sont :


    S → AB | ε
    A → aAb | ε
    bB → Bbb
    B→ε
    1) Déterminer L(G).
    2) Construire une grammaire de type 2 équivalente à G.

    EXERCICE 9 : Soit la grammaire G dont les règles de production sont :


    S → RD
    R → aRb | A
    Ab → bbA
    AD → ε
    Mêmes questions, pour G, que l’exercice 8.

    EXERCICE 10 : Soit l’alphabet terminal π = {a, (, ), +, *}.


    Soit L le langage des expressions arithmétiques construites sur l’alphabet π.
    Trouver une grammaire, de type 2, pour L.

    EXERCICE 11 : Ecrire une grammaire pour générer les identificateurs d’un langage comme Pascal. On
    considérera qu’un identificateur est valide s’il commence par une lettre alphabétique (majuscule
    ou minuscule) qui peut éventuellement être suivie d’une ou plusieurs lettres alphabétiques et/ou chiffres.
    Pour ce qui est des non terminaux de cette grammaire on pourra utiliser par exemple <Id1>, <Id2>,
    <Id3>, <Lettre>, <Chiffre>, …

    EXERCICE 12 : Soit L le langage défini sur l’alphabet π = {a, b, c, #} comme suit : L = { an b cn # / n≥0 }.
    L peut être engendré par la grammaire suivante : G = (π, {S, A}, S, P) où P est donné par :
    S → A#
    A → aAc | b
    On demande d’écrire, à partir de G, un programme Pascal qui lit des chaînes de caractères et détermine
    si elles appartiennent à L ou non.
    Indication : associer à chaque non terminal de G une procédure Pascal.

    Théorie des Langages – série n° 1 Page 2 sur 2 2014/2015

    Vous aimerez peut-être aussi