Grammaires formelles :

Règles de réécriture et grammaires

Karën Fort

[Link]@[Link] / [Link]

1 / 46
Quelques sources d’inspiration
par ordre d’importance décroissant

I Introduction à la calculabilité (Pierre Wolper) – InterEditions,

1991
I cours de D. Battistelli (Paris 3), grâce aux notes de C. Riquier
(Master 2, Paris 4)
I cours d’A. Rozenknop (Paris 13)
I cours en ligne de J-F. Perrot (Paris 6), avec son accord :
[Link]
Perrot/inalco/Automates/[Link]

2 / 46
Sources

Introduction
Rappels sur la théorie de Chomsky
Les grammaires par l’exemple
Mise en perspective

Règles de réécriture

Grammaire formelle

Pour finir

3 / 46
Une « grammaire » innée

Comment sommes-nous capables de

I former des phrases jamais entendues auparavant ?
I savoir que telle phrase appartient à la langue (= est correcte) ?

Selon Chomsky (qui a évolué sur le sujet)

L’humain possède une compétence linguistique
= savoir linguistique implicite indépendant des facteurs qui peuvent
venir influencer l’acte concret de parole (performance)

4 / 46
Définition de la langue

La langue est pour Chomsky :

I un ensemble infini de phrases
I produit grâce à un ensemble fini d’éléments
I jugées grammaticales par les sujets parlants

5 / 46
Projet de Chomsky

Mettre en lumière des règles formelles sous-jacentes à la langue

→ comprendre le mécanisme :
I comment se combinent entre eux les différents constituants
d’une phrase : ces combinaisons ne sont pas arbitraires
I structure de la phrase

Grammaires formelles = modèles théoriques qui acceptent ou

rejettent une certaine suite d’éléments

6 / 46
Exemple : exercice

Quelques règles permettant de construire des phrases du français :

I une phrase est de la forme sujet verbe
I un sujet est un pronom
I un pronom est il ou elle
I un verbe est dort ou écoute

Quelles sont les phrases que permet cet ensemble de règles ?

7 / 46
Exemple : solution

1. il écoute
2. il dort
3. elle écoute
4. elle dort

8 / 46
Grammaire et automate

Une grammaire :
I est un ensemble de règles (du type de celles présentées dans
l’exemple précédent)
I donne une description générative d’un langage
→ comment construire des éléments appartenant au langage

Un automate :
I donne une description analytique d’un langage :
→ procédé pour reconnaître les éléments du langage

→ complémentaires

9 / 46
Sources

Introduction

Règles de réécriture
Lien avec les grammaires
Définition
Dérivation
Par la pratique

Grammaire formelle

Pour finir

10 / 46
Grammaire et règles de réécriture (ou de production)

Quand peut-on décider qu’un assemblage de mots est une phrase

ou pas ?

→ on peut énoncer des règes qui permettent de distinguer des

phrases grammaticales des phrases non grammaticales
= règles de grammaires assimilables à des règles de réécriture qui
entrent dans un système formel

→ construire la grammaire d’une langue donnée revient à formuler

de façon explicite les règles d’un système de réécriture qui
engendrent cette langue

11 / 46
Formalisation des règles de production

x −→ w (x se réécrit en w )
où :
I x et w sont des chaînes sur V (vocabulaire)
I x ne peut être vide (x ∈ V + )

12 / 46
Exemple

V = {a, b, c}


 ba −→ ab
 (1)
P= ca −→ ac (2)

cb −→ bc (3)


13 / 46
Réécriture et dérivation

Définition 1
Une chaîne u1 se dérive en une chaîne u2 (u1 =⇒∗ u2 ) si une
succession de réécritures permet d’obtenir u2 à partir de u1 .

Définition 2
Une dérivation est une succession de réécritures.

14 / 46
Exercice 1
12675 est-il pair ou impair ?

V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, I , P}

0 −→ P (1)



1 −→ I



 (2)





 2 −→ P (3)

3 −→ I (4)





4 −→ P (5)





5 −→ I (6)





6 −→ P (7)


P=


 7 −→ I (8)




 8 −→ P (9)

9 −→ I (10)





IP −→ P (11)





PI −→ I (12)





PP −→ P




 (13)

II −→ I (14)
15 / 46
Correction de l’exercice 1
12675 est-il pair ou impair ?

(11) (12) (14)

12675 =⇒∗ IPPII −→ PPII −→ II −→ I

16 / 46
Exercice 2 : à vous !

V = {(, ), [, ], {, }, <, >}

Les règles de réécriture sont les suivantes :

() −→ ε (1)



 [] −→ ε

(2)
P=
 {} −→ ε (3)



<>−→ ε (4)

L’ensemble des mots qui peuvent se réécrire en ε est

exactement l’ensemble des mots bien parenthésés

Décomposez le processus pour le mot

"([]{<<>>}([(){<>}]))"

17 / 46
Exercice 3 : à vous !

V = {C , V , E , +}

CV −→ VC (1)







 VC −→ E (2)

 VEC −→ E (3)



P= VE −→ +V (4)

 V + V −→ +V (5)




EC −→ C + (6)






C + C −→ C + (7)

1. Donner la dérivation détaillée et la longueur de la dérivation

de : CVCVCV =⇒∗ E

18 / 46
Sources

Introduction

Règles de réécriture

Grammaire formelle
Définition
Grammaire et langage

Pour finir

19 / 46
Notations

I V : vocabulaire

20 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)

21 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)

22 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN

23 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN
→ VT ∩ VN = ∅ (aucun élément en commun)

24 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN
→ VT ∩ VN = ∅ (aucun élément en commun)
I P : axiome ou symbole de départ, unique (élément de VN )

25 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN
→ VT ∩ VN = ∅ (aucun élément en commun)
I P : axiome ou symbole de départ, unique (élément de VN )
I R : ensemble de règles de réécriture de la forme : α −→ β
avec

26 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN
→ VT ∩ VN = ∅ (aucun élément en commun)
I P : axiome ou symbole de départ, unique (élément de VN )
I R : ensemble de règles de réécriture de la forme : α −→ β
avec
I α, β ∈ V ∗

27 / 46
Notations

I V : vocabulaire
I VT : vocabulaire terminal fini (c’est sur ce vocabulaire que
sont formées les chaînes définies par la grammaire)
I VN : vocabulaire non-terminal fini (vocabulaire auxiliaire,
contenant les éléments du métalangage)
→ V = VT ∪ VN
→ VT ∩ VN = ∅ (aucun élément en commun)
I P : axiome ou symbole de départ, unique (élément de VN )
I R : ensemble de règles de réécriture de la forme : α −→ β
avec
I α, β ∈ V ∗
I α 6= ∅

28 / 46
Grammaire formelle

I V : vocabulaire
I VT : vocabulaire terminal
I VN : vocabulaire non-terminal
I P : axiome, ou symbole de départ (élément de VN )
I R : ensemble de règles de réécriture de la forme : α −→ β
avec
I α, β ∈ V ∗
I α 6= ∅

Définition
G = (VN , VT , R, P)

29 / 46
Détail des notations

I VT (vocabulaire terminal) : minuscules

I VN (vocabulaire non terminal) : majuscules
I P (symbole de départ) est parfois noté S
I ε note le mot vide

30 / 46
Intuition

« L’originalité des grammaires parmi les systèmes

de réécriture est cette nécessité de "chasser les non-
terminaux" dans le processus de génération des mots du
langage »
[J-F. Perrot]

31 / 46
Exemple

I V = {S, A, B, a, b}
I S : symbole de départ
I VT : {a, b}

S −→ A (1)



S −→ B (2)





 B −→ bB

(3)
P=


 A −→ aA (4)

 A −→ ε

 (5)


B −→ ε (6)

aaaa fait-il partie du langage défini par cette grammaire ?

32 / 46
Décomposons

Le mot aaaa fait partie du langage défini par cette grammaire et il

est obtenu comme suit :
A règle S −→ A
aA A −→ aA
aaA A −→ aA
aaaA A −→ aA
aaaaA A −→ aA
aaaa A −→ ε

33 / 46
Langage

Définition
Le langage généré par une grammaire G , dénoté L(G ) est
l’ensemble des mots qui peuvent être générés par G .

Équivalence
On dit que deux grammaires G1 et G2 sont faiblement équivalentes
si :
L(G1 ) = L(G2 )

34 / 46
Décidabilité

Définition
Un langage est décidable si pour toute phrase on peut savoir au
bout d’un temps fini si elle appartient ou nom au langage.

35 / 46
Sources

Introduction

Règles de réécriture

Grammaire formelle

Pour finir
CQFR : Ce Qu’il Faut Retenir
TD

36 / 46
I théorie de Chomsky
I règles de réécriture :
I définition
I manipulation

I grammaires formelles :
I définition
I manipulation
I lien langage / grammaire

37 / 46
Exercice 1 : à faire, à rendre à la fin du TD

Soit la grammaire G1 définie par :

VN = {A, S}
VT = {a, b, c}


 S −→ AcA
 (1)
P= A −→ a (2)

A −→ b (3)


L(G1 ) ?

38 / 46
Exercice 2 : à faire, à rendre à la fin du TD

Soit la grammaire G2 définie par :

VN = {S}
VT = {a, b, c}

S −→ aca (1)



 S −→ acb

(2)
P=
 S −→ bcb
 (3)


S −→ bca (4)

Que pouvez-vous dire de L(G2 ) ? et de G2 ?

39 / 46
Exercice 3 : à faire, à rendre à la fin du TD
Soit la grammaire G3 définie par :
VN = {S, GN, GV , D, N, V }
VT = {le, la, gâteau, fille, mange, déguste}

S −→ GN GV (1)



GV −→ V GN (2)









 GN −→ D N (3)




 D −→ le (4)
P= D −→ la (5)

N −→ fille (6)





N −→ gâteau (7)









 V −→ déguste (8)

V −→ mange (9)

L(G3 ) ?
40 / 46
Exercice 4 : à faire, à rendre à la fin du TD

Soit la grammaire G4 définie par :

VN = {S, A, B}
VT = {a, b}

S −→ AB (1)



 S −→ AS

(2)
P=
 A −→ a
 (3)


B −→ b (4)

L(G4 ) ?

41 / 46
Exercice 5 : à faire, à rendre à la fin du TD

Soit la grammaire G5 définie par :

VN = {S}
VT = {z}

S −→ zSz (1)

P=
S −→ z (2)

L(G5 ) ?

42 / 46
Exercice 6 : à faire, à rendre à la fin du TD
Soit la grammaire G6 définie par :
VN = {S, GN, GV , Df , Dm, Nf , Nm, V }
VT =
{un, une, le, la, enfant, garçon, fille, cerise, haricot, cueille, mange}

S −→ GN GV (1)



GN −→ Df Nf|Dm Nm (2)





GV −→ V GN (3)





Df −→ une|la (4)


P=


 Dm −→ un|le (5)




 Nf −→ fille|cerise (6)

Nm −→ enfant|garçon|haricot (7)





V −→ cueille|mange (8)

« un haricot cueille un enfant » appartient-elle à L(G6 ) ?

43 / 46
Exercice 7 : à faire, à rendre à la fin du TD

Construire une grammaire G7 pour le langage

L(G7 ) = {ab n a|n ∈ N}

44 / 46
Exercice 8 : à faire, à rendre à la fin du TD

Construire une grammaire G8 pour le langage

L(G8 ) = {02n 1n |n ≥ 0}

45 / 46
Exercice 9 : à faire, à rendre à la fin du TD

Soit la grammaire G9 définie par :

VN = {S, A, B}
VT = {a, c}

S −→ ASA (1)







 AAS −→ B (2)

 AB −→ B (3)



P= AA −→ a (4)

aA −→ c (5)





Ba −→ ca (6)






Bc −→ ac (7)

1-1-2-4-6 et 1-1-1-1-1-2-4-5-4-4-5-6 vont donner ?

46 / 46