REPUBLIQUE DU TCHAD UNITE-TRAVAIL-PROGRES

**********
UNIVERSITÉ POLYTECHNIQUE DE MONGO
**********
FACULTE DES SCIENCES FONDAMENTALES
**********
DÉPARTEMENT DE MATHEMATIQUES-INFORMATIQUE
**********
ANNÉE : 2022-2023
**********
NIVEAU : LICENCE 2

GROUPE N°4

THEME : LA FORME NORMALE DE

GREIBACH

NOMS ET PRENOMS DES EXPOSANTS :

DAOUNA BRAIKEUTCHIKI GONTRAN

DJEMADJI ODJIEL BILL CLINTON
DJERAKOULA ARSENE
DJIMSAMADJI THEOPHILE
MBAIRAKOULA ROMARIC

Charge de cours : Mr. MAHAMAT

TETEDJIMA SEYOA

1
 PLAN DU TRAVAIL
INTRODUCTION
I. LE LANGAGE ALGEBRIQUE
II. LES AUTOMATES A PILES
a) Pourquoi une pile ?
b) Exemple préliminaire
c) Définition formelle
d) Fonctionnement
III. LA FORME NORMALE DE CHOMSKY
IV. LA FORME NORMALE DE GREIBACH (FNG)
CONCLUSION

2
 INTRODUCTION
En informatique théorique, et notamment en théorie de langage formelle,
une grammaire algébrique est en forme de Greibach (Greibach normal
form) si les membres droits de ces règles commencent par un symbole
terminal, suivi éventuellement d’une ou plusieurs variables. Une variante
permet une règle additionnelle pour engendrer le mot vide s’il fait partie
du langage. Cette forme normale porte le nom de Sheila Greibach qui l’a
introduite et a prouvé son existence. Pour s’imprégner de la forme
normale de Greibach, il est nécessaire de comprendre ce que c’est un
langage algébrique (ou grammaire hors-contextuelle) ainsi que un
automate à pile ? En nous situant comme repère ces interrogations nous
expliquerons la forme normale de Greibach dans le contenu de notre
travail.

3
 I. LE LANGAGE ALGEBRIQUE
En théorie de langage formelle, un langage algébrique ou langage non-
contextuel est un langage qui est engendré par une grammaire
algébrique. De manière équivalente, un langage algébrique est un langage
reconnu par un automate à pile. Les langages algébriques forment les
langages de suite 2 dans la hiérarchie de Chomsky.
Exemple : {anbn/n≥0} = {ԑ, ab, aabb, aaabbb, …..} est l’exemple type
d’un langage algébrique qui n’est pas un langage rationnel : il est formé
des mots qui ont autant de lettre a que de lettre b, et avec la condition
supplémentaire que les lettres a précédant les lettres b.

II. LES AUTOMATES A PILES

L’automate à pile AP va tenter de lire le mot aaabbb :

a) Pourquoi une pile ?

• Les automates finis (AEF) n’ont pas d’autre mémoire que leurs états
• Ils ne savent donc pas « compter » au-delà de leur nombre d’états
• Une pile utilise une mémoire additionnelle non bornée
• On accède à la pile uniquement par son sommet
• Le nombre de symboles utilisés dans la pile est fini
• La pile vide peut être un critère d’acceptation de mots.

b) Exemple préliminaire

Les étapes de reconnaissance du langage {anbn, n ≥ 1} par un AP

pourraient être les suivantes :
1. Lire les a, les stocker dans la pile et ne pas changer d’état
2. A la rencontre du premier b, dépiler un a et changer d’état
3. Dépiler un a pour chaque b rencontré

4
4. Si les a de la pile se terminent au même moment que les b lus, alors le
mot appartient au langage.

c) Définition formelle

Un AP est défini formellement par un septuplé (Vt, W, Q, q0, Z0, f, F) où :

• Vt est l’alphabet d’entrée, fini et non vide
• W est le vocabulaire de la pile, fini et non vide
• Q est l’ensemble d’états, fini et non vide
• q0 est l’état initial qui appartient à Q
• Z0 est le symbole initial de la pile (fond de la pile), Z0∈W
• F est l’ensemble des états finaux (d’acceptation), F⊂Q
• f est la fonction de transition

d) Fonctionnement

Une règle f(q, a, p) = (q’, χ ) de transition considère :

• l’état courant q de l’automate

• le caractère lu a sur le ruban (ou peut-être pas : ε)
• le symbole p de sommet de pile (ou peut-être pas : ε)
Une règle indique :
• le prochain état q’ de l’automate
• la suite de symboles χ à empiler à la place du sommet de pile

III. LA FORME NORMALE DE CHOMSKY

On limite la forme des productions :

seules sont admises les formes A → BC et A → a.
Une telle grammaire est une grammaire normale de Chomsky.

Théorème : Tout langage non contextuel sans le mot vide peut être
engendré par une grammaire normale de Chomsky.

Démonstration :
1. Partir de G sans variable inutile ni ε-production ni production
unitaire ;
2. Pour chaque terminal a, ajouter une variable Ca avec l'unique
production C a → a ;

5
 3. Soit A → X1X2...Xm une production de G avec m > 1.
Remplacer toutes les occurrences des terminaux par la variable
associée au 2.
4. Les productions sont de la forme désirée ou bien de la forme
A→B1B2...Bm où m > 2 et où les Bi sont des variables. Remplacer
une telle production par A→ B1D1, D1 → B2D2, …

Exemple : S → aB | bA A→ a | aS | bAA B → b | bS | aBB

devient :
S → CaB | C bA C a → a C b → b
A→ a | CaS | CbD D → AA
B → b | C bS | C aE E → BB
La forme normale de Chomsky a un intérêt essentiellement
théorique.

IV. LA FORME NORMALE DE GREIBACH (FNG)

Une grammaire algébrique est en forme normale de Greibach si toutes

ses règles sont de la forme :

A→a A1A2 ...Am ou S→ ε

où A est une variable, a est une lettre et A1A2 ...Am suite éventuellement
vide de variables ; S est l'axiome et ε est le mot vide .

Une grammaire en forme normale de Greibach est notamment

sans récursivité gauche. La propriété principale est que toute

grammaire algébrique peut être transformée en une grammaire

équivalent en forme normale de Greibach, théorème établi en

1965 par Sheila Greibach .

En forme normale de Greibach, une dérivation engendre, à chaque

pas de dérivation, une lettre d'un mot du langage donnée : la
longueur de la dérivation est donc égale à la longueur du mot. La
forme normale peut être utilisée, de manière équivalente, pour
construire une automate à pile qui accepte les mots du langage
en temps réel, c'est-à-dire qui lit une lettre du mot d'entrée à
chaque pas de calcul.

6
Construction

La construction d'une grammaire en forme normale de Greibach à

partir d'une grammaire algébrique donnée par partie des sujets
traités dans de nombreux manuels d'informatique théorique sur
les langages formels, les automates et leur complexité. Une des
constructions est en plusieurs phases :

Phase préliminaire : suppression des epsilon-règles

Article détaillé : Élimination des ε-règles.
On peut supposer que l'axiome de la grammaire ne figure pas
dans un membre droit de règle .
Une règle A→ ε, A où n'est pas l'axiome, est supprimée ; on considère
chaque règle B→α pour chaque occurrence où A figure dans α, et on
ajoute, pour chaque occurrence α = βAγ, la règle B→ βγ à la grammaire,
sauf si on crée une epsilon-règle. Par exemple, si
B→ aAbAc on ajoute les trois règles B→ abAc, B→ aAbc, B→ abc
Un règle dont le membre droit contient
variables qui toutes
dérivent en le mot vide peut ainsi donner jusqu'à
règles.

Deuxième phase : suppression des règles unité

Article détaillé : Suppression des règles unité.

Une règle unité est une règle de la forme A→B, où B est une
variable. Pour éliminer ce type de règles, on remplace une telle
règle par la règle A→α, pour chaque règle B→α .
(sauf si c'est une règle unité précédemment enlevée [5] ). Cette
technique est complétée dans le cas de cycles (comme
l'existence de trois règles A→B, B→C, C→A) par
l'identification des variables d'un cycle : elles sont toutes
remplacées par l'une d'entre elles.

Mise sous forme normale

On suppose la grammaire sans ε-règles et sans règles unité. On

suppose les variables numérotées en A1, A2,…, Am
définit une suite G0, G1,…,Gn de grammaires, où G0 est la grammaire
initiale, avec la propriété que dans Gi,
, les variables A1,…, An n'apparaissent pas en tête des membres droits de
la règle. On suppose la grammaire Gi-1 construite, et on procède en deux
étapes
1. Suppression de la récursivité gauche pour Ai :

on supprime les Ai en tête de la règle Ai :

Les règles Ai→Aiα1 /../Aiαn/.../ β1/.../βm ou βj ne commence pas A sont
remplacées par :
Ai→β1A’i/.../ βmA’i/ β1/.../ βm

7
A’i→α1A’i/…./ αnA’i/α1/.../ αn

Exemple

Voici un exemple tiré du livre d'Olivier Carton [6] (on écrit A, B, C au

lieu de ):

Grammaire G0 :

Exemple : A1→ A2A3 A2→ A3A1 | bA3→ A1A2 |a

Première étape : A1 et A2 sans changements ; pour A3, garder A3 →a ;
puis A3→A2A3A2 , puis A3 →A3A1A3A2 |bA3A2 ; les productions de
A 3 sont donc : A3 → A3A1A3A2 et A3→bA3A2 |a.
Élimination de la récursivité directe à gauche :
A3 → bA3A2 |a|bA3A2B3 |aB3 et B3→A1A3A2 |A1A3A2B3.
Comme prévu, les productions de A 3 sont de type 2. Utilisons-les pour
récrire les productions de A 2 :
A2 → bA3A2A1 |aA1 |bA3A2B3A1 |aB3A1 |b.
Récrivons maintenant les productions de A 1 :
A1 → bA3A2A1A3 |aA1A3 | bA3A2B3A1A3 |aB3A1A3 | bA3,
puis les productions de B3 :
B3 → bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A2B3A1A3A3A2 |
aB3A1A3A3A2 | bA3A3A2 |
bA3A2A1A3A3A2B3 | aA1A3A3A2B3 | bA3A2B3A1A3A3A2B3 |
aB3A1A3A3A2B3 |bA3A3A2B3.

Forme normale quadratique

Un grammaire est sous forme normale quadratique de Greibach

si toutes ses règles sont de la forme

où est composé d'au plus deux variables, donc si de plus les

membres droits de règles sont de longueur au plus 3. La grammaire
ci-dessus, et la grammaire :

8
du langage de Lukasiewicz sont sous forme quadratique, la
grammaire

ne l'est pas. On peut la transformer en grammaire quadratique en

groupant les occurrences consécutive ; ici, on introduit une nouvelle
variable et on remplace la grammaire par :

La grammaire n'est plus sous forme normale de Greibach, mais

comme précédemment, on remplace la variable de tête dans la

règle pour , ce qui donne , d'où

9
 CONCLUSION

En somme, ce travail nous a permis d’approfondir nos connaissances en

compilation et en particulier sur la forme normale de Greibach qui est
une grammaire de type deux selon la classification de Chomsky. Cette
forme de Greibach est définie comme une grammaire de type deux mais
commençant par un terminal suivi par une variante(un symbole terminal,
un symbole fini non terminal).

10