Introduction aux
grammaires
Université Libre de Bruxelles
2008 - 2009
Denis BOIGELOT Sébastien COLLETTE Gilles GEERAERTS
Exemple
Soit une grammaire G dont les règles de P sont :
S " aSbS
bSaS
e
S est la seule variable (ou symbole non-terminal) ;
il est aussi le symbole de départ.
On a T = {a, b, e}.
Définition
Une grammaire est un quadruplet G = !V , T , P, S " où
• V est l’ensemble des variables ;
• T est l’ensemble des terminaux ;
• P est l’ensemble des règles de production avec
P ! (V " T )V(V " T ) ! (V " T )* ;
• S # V est le symbole de départ.
Arbre de dérivation
Pour le mot abeaebe, selon G:
S
a
S
b
a
b
S
e
S
e
S
e
Dérivation à gauche: S $ aSbS $ abSaSbS $ abeaSbS
$ abeaebS $ abeaebe
Conclusion: abeaebe # L(G)
Hiérarchie de Chomsky
Hiérarchie de Chomsky
• Classe 0: grammaire non restreinte
• pas de restrictions sur la forme des règles
• reconnue par une machine de Turing
• Classe 1: grammaire context-sensitive
Publicité
• toute règle est de la forme : #A$ " #%$, avec
% # (V " T)+ et #,$ # (V " T)*
• on peut avoir la règle S " &, si S n’apparaît
dans aucun membre de droite
• reconnue par une machine de Turing non-déterministe à
ruban de longueur bornée par un multiple fixé de la longueur
du mot d'entrée.
Hiérarchie de Chomsky
Hiérarchie de Chomsky
• Classe 2: Grammaires context-free
• toute règle est de la forme : A " #
• reconnue par un automate à pile non
déterministe
• Classe 3: grammaires régulières (2 types)
• grammaire linéaires droites règles du type :
A " wB ou A " w
• grammaires linéaires gauches règles du
type : A " Bw ou A " w
• reconnue par un automate fini
Exemples
G’: grammaire
context-free
1. S " aSb
2. S " &
Classe 1
n n n
0 1 2
Classe 2
n n
0 1
Classe 3
(0+1)*
G: grammaire
context-sensitive
1. S " ABS
2. BA " AB
3. BS " b
4. Bb " bb
5. Ab " ab
6. Aa " aa
L(G) = L(G’) = {anbn}
L(G) est un langage context-free (et donc aussi context-
sensitive) bien que ça grammaire ne l’est pas
Publicité
Exercice 1
Décrivez, en français, les langages générés par les
grammaires suivantes, et donnez leur type:
1. S " abcA
" Aabc
A " &
Aa " Sa
cA " cS
2. S " 0
" 1
" 1S
3. S " a
" *SS
" +SS
Solution 1
1. Grammaire non restreinte donnant toutes les
suites de abc.
2. Grammaire linéaire droite donnant toutes les
suites de 1 éventuellement terminées par un 0,
ou bien le string 0.
3. Grammaire context-free donnant toutes les
expressions arithmétiques utilisant la somme et
le produit sur la variable a, et ce, en notation
polonaise.
Exercice 2
Soit la grammaire G suivante :
S " AB
A " Aa
bB
B " a
Sb
Cette grammaire est-elle régulière ?
Donnez l’arbre de dérivation pour baabaab, bBABb et baSb
Donnez les dérivations gauche et droite de baabaab.
Solution 2
Il s’agit d’une grammaire context-free mais pas
régulière. Justification : il ne peut pas y avoir à la
fois une règle de la forme A " #B et une règle de
la forme A " B$ dans une grammaire régulière.
Solution 2
S
A
B
Publicité
b
B
S
b
A
B
Solution 2
A
b
A
B
a
S
a
S
A
b
B
a
b
B
B
a
Solution 2
S
A
B
S
b
b
B
a
Solution 2
Exercice 3
1. La dérivation gauche de baabaab est : S $
AB $ AaB $ bBaB $ baaB $ baaSb $
baaABb $ baabBBb $ baabaBb $ baabaab
2. La dérivation droite est : S $ AB $ ASb $
AABb $ AAab $ AbBab $ Abaab $
Aabaab $ bBabaab $ baabaab
Solution 3
S " bSa|aSb|abS|baS|Sab|Sba|Sa|aS|a
On dérive baaba de la façon suivante :
Publicité
S $ baS $ baabS $ baaba
1. Écrivez une grammaire context-free qui génère
toutes les chaînes de a et de b (dans n’importe quel
ordre), tel qu’il y a plus de a que de b. Testez votre
grammaire sur baaba en en donnant une dérivation.
2. Écrivez une grammaire context-sensitive qui
génère toutes les chaînes de a, de b et de c (quel
que soit l’ordre), ayant le même nombre de a, de b
et de c. Donnez la dérivation de cacbab selon votre
grammaire.
Solution 3
S " ABCS | &
AB " BA
AC " CA
BA " AB
BC " CB
CA " AC
CB " BC
A " a
B " b
C " c
S $ ABCS $ ABCABCS $ ABCABC $
ACBABC $ CABABC $ CABACB $ CABCAB
$ CACBAB $ cACBAB $ caCBAB $ cacBAB
$ cacbAB $ cacbaB $ cacbab
Exercice 4
1. Écrivez une grammaire context-free pour les
langages 0i1n2n et 0n1n2i, avec n,i > 0
2. Montrer que soient L1 et L2 deux langages context-
free, L1 ' L2 n’est pas nécessairement context-free.
Solution 4
S " AB
S " AB
A " 0A | 0
A " 0A1 | 01
B " 1B2 | 12
B " 2B | 2
1. Les langages L1 = {0i1n2n | n > 0, i > 0} et L2 =
{0n1n2i | n > 0, i > 0} sont context-free, alors que
L1 ' L 2 = {0n1n2n | n > 0} ne l’est pas
2. Soient L1 = % et L2 = {0n1n | n > 0} deux langages
context-free, on a L1 ' L 2 = % qui est context-free