Cours theorie des langages grammaires Théorie

Théorie des langages : Cours theorie des langages langages grammaires

Télécharger PDF

Chapitre 2 : Les grammaires et les langages

Théorie des langages

Partie 1 : Langages et grammaires

Définitions de langages

Si un langage est fini, on peut le définir en énumérant tous ses mots. On dit qu’il est défini par extension.

Si un langage est infini, on peut le définir à travers les propriétés de ses mots. On dit qu’il est défini par compréhension. Ce langage peut être décrit par un ensemble de règles qui expliquent comment générer ces mots.

Exemple 1 : Définition d’un ensemble d’identificateurs

Soit le vocabulaire V = {A, B, ..., Z, a, b, ..., z, 0, 1, ..., 9}. À partir de V, on veut définir l’ensemble des identificateurs. Soit L cet ensemble.

L = {ident ∈ V* | ident commence par une lettre suivie d’une chaîne de chiffres et de lettres éventuellement vide}.

Un identificateur se compose de lettres concaténées avec une chaîne de lettres et de chiffres.

Une lettre se compose de a ou b ou ... ou z ou A ou B ou ... ou Z.

Une chaîne de lettres et de chiffres se compose de :

• une lettre concaténée avec une chaîne de lettres et de chiffres,
• un chiffre concaténé avec une chaîne de lettres et de chiffres,
• ou le mot vide.

Un chiffre se compose de 0 ou 1 ou ... ou 9.

Version formalisée de l’exemple 1

La concaténation est remplacée par un point (.) et l’union est remplacée par une barre verticale (/).

Version 1 :

ident → lettre . chaîne_lettres_chiffres

lettre → a / b / ... / z / A / B / ... / Z

chaîne_lettres_chiffres → lettre . chaîne_lettres_chiffres / chiffre . chaîne_lettres_chiffres / ε

chiffre → 0 / 1 / ... / 9

Définition formelle d’une grammaire

Une grammaire est un quadruplet : G = <VT, VN, S, R>, où :

• VT : Vocabulaire terminal (en minuscules), alphabet du langage.
• VN : Vocabulaire non-terminal (en majuscules), avec VN ∩ VT = ∅.
• S : Axiome ou symbole de départ, S ∈ VN.
• R : Ensemble de règles de la grammaire.

Une règle de la forme u → v, où u ∈ (VT ∪ VN)* et v ∈ VT*, est appelée règle terminale.

Si plusieurs règles partagent la même partie gauche, on peut regrouper leurs parties droites en utilisant ‘|’.

Exemple 1 appliqué à une grammaire

Pour l’exemple 1 : G1 = <VT, VN, S, R>, où :

• VT = {A, B, ..., Z, a, b, ..., z, 0, 1, ..., 9}.
• VN = {IDENT, LETTRE, CHIFFRE, CHAINE_LETTRES_CHIFFRES}.
• S = IDENT.
• R = {

IDENT → LETTRE . CHAINE_LETTRES_CHIFFRES,

CHAINE_LETTRES_CHIFFRES → LETTRE . CHAINE_LETTRES_CHIFFRES / CHIFFRE . CHAINE_LETTRES_CHIFFRES / ε,

LETTRE → a / b / ... / z / A / B / ... / Z,

CHIFFRE → 0 / 1 / ... / 9.

}

Dérivation

La notation u ⇒ v signifie que v dérive de u dans la grammaire G, ou que u est remplacé par v selon les règles de G.

Étapes de dérivation

Soit une grammaire G = <VT, VN, S, R>. Soient u ∈ VT* et v ∈ VT*.

G permet de dériver v de u en une étape (u ⇒ v) si et seulement si :

• u = x u' y (x et y peuvent être vides),
• v = x v' y (x, v', y peuvent être vides),
• u' → v' est une règle de R.

G permet de dériver v de u en plusieurs étapes (u ⇒* v) si et seulement si ∃ k ≥ 0 et ∃ v₀, ..., vₖ ∈ VT* tels que :

• u = v₀,
• v = vₖ,
• vᵢ ⇒ vᵢ₊₁ pour 0 ≤ i < k.

Dans le cas général, on écrit : (u ⇒* v) si et seulement si ∃ vᵢ ∈ VT* pour i ∈ [0, k[ tels que u = v₀, v = vₖ et vᵢ ⇒ vᵢ₊₁ dans G.

Exemples de dérivation

Exemple 3 :

G = <VT, VN, E, R>, où :

• VT = {a, +, *, (, )},
• VN = {E, T, F},
• R : (ensemble de règles non précisé).

Exemple de dérivation : 1 + 2 * 3 → 45 + 6124 → 613466.

Mots générés par une grammaire

Soit G = <VT, VN, S, R>. Les mots générés par G sont ceux de VT* dérivés à partir de l’axiome S, donc S ⇒* v.

Langage généré par une grammaire

Un langage généré par G est l’ensemble des mots v ∈ VT* qui peuvent être dérivés à partir de S :

L(G) = {v ∈ VT* | S ⇒* v}.

Remarque :

• Une grammaire définit un seul langage.
• Un langage peut être défini par plusieurs grammaires.

Exemple 4 : Grammaire générant des mots de la forme aⁿ

G = <VT, VN, S, R>, où :

• VT = {a},
• VN = {S, S₁},
• R = {S → a S₁, S₁ → a S₁, S₁ → ε}.

L(G) = {w ∈ VT* | w = aⁿ, n ≥ 0}.

Exemples :

• S → a S₁ ⇒ a a ∈ L(G).
• S → a S₁ ⇒ a a S₁ ⇒ a a a ∈ L(G).

Exemple 5 : Grammaire équivalente à G

G' = <VT, VN, S, R>, où :

• VT = {a},
• VN = {S},
• R = {S → a S, S → a}.

L(G') = {w ∈ VT* | w = aⁿ, n ≥ 1}.

Remarque : L(G) ≠ L(G') car S → a ∈ L(G') mais S → a ∉ L(G).

Exemple 6 : Trouver une grammaire pour L1 = {(ab)ⁿ a^m | n ≥ 0, m ≥ 0}

Soit VT = {a, b} et L1 = {(ab)ⁿ a^m | n ≥ 0, m ≥ 0}.

Exemple 7 : Trouver une grammaire pour L3 = {abⁿ a | n ≥ 0}

Soit VT = {a, b} et L3 = {abⁿ a | n ≥ 0}.

Exemple 8 : Trouver une grammaire pour L4 = {aⁿ b^m c^p | n, m, p ≥ 0}

Soit VT = {a, b, c} et L4 = {aⁿ b^m c^p | n, m, p ≥ 0}.

FAQ

1. Qu’est-ce qu’une grammaire par extension ?

Une grammaire par extension définit un langage fini en énumérant tous ses mots possibles.

2. Comment formaliser une grammaire pour un langage infini ?

On utilise un quadruplet <VT, VN, S, R> où VT est l’alphabet terminal, VN les symboles non-terminaux, S l’axiome et R l’ensemble des règles de dérivation.

3. Pourquoi deux grammaires peuvent-elles générer le même langage ?

Deux grammaires peuvent générer le même langage car elles peuvent utiliser des règles différentes mais équivalentes pour dériver les mêmes mots.