Grammaire
• C’est un quadruplé: (T,N,S,P) où:
1. T ensemble des terminaux;
2. S: l’axiome (Point de départ);
3. N: ensemble des non terminaux;
4. P les règles de production.
PS: une règle de production correcte doit toujours contenir au moins un non terminal à
gauche de la flèche. (a→aa, n’est pas une règle de production correcte).
Exemple: Soit G une grammaire définie par les règles de production suivante:
S→aS/B
B→bB/C
C→cC/c
T={a,b,c}, N={S,B,C}, l’axiome: S, P est l’ensemble des 6 règles.
Langage généré par la grammaire de l’exemple:
S→aS(1) / B(2)
B→bB(3) / C(4)
C→Cc(5) / ε(6)
Point de départ c’est S:
S ├ aS├ aaS ├* anS ├ anB ├ anbB ├ anbbB ├* anbmB ├ anbmC ├
anbmCc ├* anbmCck ├ anbmck
L(G)={an bm ck, n≥0,m≥0, k ≥0}
Autres grammaires générant le même langage : L(G)={an bm ck,
n≥0,m≥0, k ≥0}
S→ABC
A→aA / ε
B→bB / ε
C→cC / ε
----------------------------------------------------------------------------------------
S→aS / Sc/B
B→bB / ε
Exemple 2 :
L(G)={an bn , n≥1}, les grammaires suivantes generent elles Ce langage?
S→AB
L(G)={a b ,n,m≥0}
n m
A→aA / ε
B→bB / ε
-----------------------------------------------------------------
S→aS / Sb/ab L(G)={a b ,n,m≥1}
n m
-----------------------------------------------------------------
S→abS / ε L(G)={(ab) , n≥0} n
-----------------------------------------------------------------
S→aSb / ε L(G)={a b ,n≥0}
n n
-----------------------------------------------------------------
S→aSb / ab (Correcte)
Exemple 3:
L(G)={an bm , n≥m ≥ 1}
Cette Grammaire génère -t- elle le ce langage?
S→aSb / a
On se pose la question sur le mot aaab? Appartient il au langage
L? Peut il être généré par cette grammaire?
L(G)={an+1 bn , n≥0}
• Exemple 3: L(G)={an bm , n≥m ≥ 1}
Cette Grammaire génère -t- elle le ce langage?
S→aS / Sb/ A
A→aA / ε
Le mot abb peut-il être généré par cette grammaire? Appartient-il au
langage L?
L(G)={an bm , n,m≥0}
------------------------------------------------------------------------------------------
S→aSb / A
A→aA / a
Le mot ab peut-il être généré par cette grammaire? Appartient-il au
langage L?
L(G)={an bm , n>m≥0}
Exemple 3: L(G)={an bm , n≥m ≥ 1}
Voici des grammaires générant ce langage.
S→aSb / aAb
A→aA / ε
--------------------------------------------------------------------
S→aSb / A
A→aA / ab
-------------------------------------------------------------
S→aSb / aS/ab
Exemple 4: L(G)={ω{a,b}*, ІωІa ≡0[3]}
Laquelle de ces solutions est correcte?
S→aaaS / bS / ε
Le mot ababa appartient-il au langage? Peut-il être généré par cette
grammaire?
---------------------------------------------------------------
S→ bS / aA / ε
A→bA / aB
B→bB / aS
• Exemple 5 : L(G)={an bn cn , n≥0}
Utilisation des permutations:
S→aSBC / ε (Avec ces deux règles nous aurons an(BC)n.)
CB →BC (A chaque fois qu’on trouve un C avant un B , on le remet
derrière).
aB →ab (S’il y des a avant le B, je serai sûr qu’il n y a pas de C avant).
bB →bb (S’il y un b avant le B, je serai sûr qu’il n y a pas de C avant).
bC →bc (S’il y un b avant le C, alors toutes les lettres sont à leur place « an
bn Cn»).
cC →cc (Transformer les autres C).
