Chapitre 4
Solution de l'exercice 5.1

Pour chacune des grammaires suivantes :

1. Les écrire sous forme BNF
2. Donner les arbres de dérivation associés aux mots donnés à l'exercice 3.1. dans le cas où la grammaire est de type 2 ou 3. Les représenter à l'aide des diagrammes de Conway

Gex1 = ({a,b,c}, {S}, S, {S → aSbSa | c}) (type 2)
"S" ::= a "S" b "S" a | c
le mot "acbca" donne l'arbre de dérivation suivant :

Gex2 = ({a,b,ch,d}, {S,A,B,C}, S, {S → BCaCbbA ; A → CaCbb | ε ; Ca → ba ; Cbb → da ; B → cha}) (type 0)
"S" ::= "B" "C" a "C" b b "A"
"A" ::= "C" a "C" b b | ε
"C" a ::= b a
"C" b b ::= d a
"B" ::= ch a

Gex3 = ({a,b}, {S,A}, S, {S → Aa | bA ; A → Sa | bS}) (type 2)
"S" ::= "A" a | b "A"
"A" ::= "S" a | b "S"
Le langage étant vide, il n'y a pas de mots à dériver !

mardi, 25/11/03 16:44