Scribd
Importer
152 vues1 page

Exercices de grammaire en informatique

Ce document contient plusieurs exercices sur les grammaires formelles. Les exercices portent sur la détermination si des mots appartiennent au langage d'une grammaire, la construction d'arbres de dérivation, et le type de grammaires données.

Transféré par

Zarai Yahia
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
152 vues1 page

Exercices de grammaire en informatique

Ce document contient plusieurs exercices sur les grammaires formelles. Les exercices portent sur la détermination si des mots appartiennent au langage d'une grammaire, la construction d'arbres de dérivation, et le type de grammaires données.

Transféré par

Zarai Yahia
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

2ème Année informatique Module : THL

TD 01

Exercice 01 :
Soit la grammaire G = ({a, b, c} , {S, A} , S, P) où P contient les règles suivantes :
S → aS | bA
A → cA | ε
Déterminer si les mots w1 = abac, w2 = aabccc, w3 = cabbac et w4 = ab sont dans L(G).

Exercice 02:
 Soit la grammaire G = ({a, b, e} , {S}, S, P) où P contient les règles suivantes :
S → aSbS
| bSaS
|e
o Donner l’arbre de dérivation du mot abeaebe

o Donner l’arbre de dérivation pour baabaab, bBABb, baSb

Exercice 03:
Quel est le type de la grammaire Gi = ({a, b, c} , {S, A, R, T} , Pi , S)
1. P1 : S → aS | aA ; A → bAc | ε
2. P2 : S → aSc | A ; A → bAc | ε
3. P3 : S → aSbS | ε
4. P4 : S → aSc | bA ;A → bA | ε
5. P5 : S → aRbc | abc ;R → aRTb | aTb ; Tb → bT ; Tc → cc
6. P6 : S → aAS | a ; A → SbA | SS | ba
7. P7 : S → aAS | SA ; aA → a

Université de Tébessa 2019/2020 Page 1

Vous aimerez peut-être aussi