Scribd
Importer
99 vues1 page

T1

Le document présente plusieurs exercices sur la théorie des langages formels et des grammaires. Il inclut des questions sur la génération de mots par une grammaire donnée, des exemples de langages et des grammaires correspondantes, ainsi que des demandes de conception d'automates pour divers langages. Chaque exercice explore des concepts fondamentaux de la grammaire et de l'automatisation dans le contexte des langages constitués des lettres a, b et c.

Transféré par

yahyaouiimen
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
99 vues1 page

T1

Le document présente plusieurs exercices sur la théorie des langages formels et des grammaires. Il inclut des questions sur la génération de mots par une grammaire donnée, des exemples de langages et des grammaires correspondantes, ainsi que des demandes de conception d'automates pour divers langages. Chaque exercice explore des concepts fondamentaux de la grammaire et de l'automatisation dans le contexte des langages constitués des lettres a, b et c.

Transféré par

yahyaouiimen
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TEST

EXERCICE 1 :
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 2 :
Pour chacun des langages suivants, donner des exemples de mots contenus dans chacun des langages,
et des grammaires qui engendrent chacun des langages (Li)i=1,..,5 :
1) L1 = { w ∈ {a, b, c}* / w commence par la lettre ‘a’ } ;
2) L2 = { w ∈ {a, b, c}* / w se termine par la lettre ‘a’ } ;
3) L3 = { w ∈ {a, b, c}* / w contient au moins une occurrence de la lettre ‘a’ } ;
4) L4 = { w ∈ {a, b, c}* / w contient au moins deux occurrences la lettre ‘a’ } ;
5) L5 = { w ∈ {a, b, c}* / w contient au moins deux occurrences consécutives de la lettre ‘a’ }.

EXERCICE 3 :
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 }
n m n-m
d) L4 = { a b c / n ≥ m ≥ 0 } i) L9 = { 0i 1j / i ≠ j, i ≥ 0, j ≥ 0 }
e) L5 = { a2n/ n ≥ 0 }

EXERCICE 4 :
Dessinez un automate pour les langages suivants :
1. Le langage des mots contenant au moins une fois la lettre a
2. Le langage des mots contenant au plus une fois la lettre a
3. Le langage des mots contenant un nombre pair de fois la lettre a
4. Le langage des mots admettant aba pour facteur :
5. Le langage des mots admettant aba pour sous-mot :

Vous aimerez peut-être aussi