Théorie des langages
Théorie des langages
Grammaires régulières, Langages informatiques · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce matériel couvre les notions fondamentales de la théorie des langages, en particulier les grammaires, leurs types, la dérivation, les arbres de dérivation, ainsi que les concepts d'ambiguïté et d'indépendance du contexte. Il s'adresse aux étudiants en informatique ou en linguistique formelle souhaitant comprendre la génération des langages par des grammaires formelles.
Une dérivation d’un mot w à partir d’une grammaire G avec le symbole de départ S, notée S * w, est une application successive d’un ensemble de règles de production en partant du symbole de départ S.
L’application d’une règle de la forme u → v consiste à remplacer la sous-chaîne u par la sous-chaîne v.
Soit G = (V, T, S, R) une grammaire. Le langage L(G) généré par G est l’ensemble des mots dérivés à partir de S :
L(G) = { w ∈ T* | S * w }
Une grammaire G = (V, T, S, R) est dite non contextuelle si les règles de production sont de la forme :
A → u
où A ∈ V et u ∈ (T + V)*.
Exemple :
G = ({S}, {a, b}, S, R) avec R = { S → aSb | ɛ }
Une grammaire G = (V, T, S, R) est dite dépendante du contexte si elle inclut au moins une règle de production qui admet à gauche plus d’un non terminal.
Exemple :
G = ({S}, {a, b}, S, R) avec
R = {
S → AB,
A → aAb | ɛ,
B → cB | ɛ
}
Le langage généré est :
L(G) = { w ∈ {a,b}* | w = a^n b^n c^m, n ≥ 0, m ≥ 0 }Un langage est dit indépendant du contexte s’il existe une grammaire non contextuelle qui le génère.
Exemples :
À chaque dérivation d’un mot à partir d’une grammaire est associé un arbre appelé arbre de dérivation (ou arbre syntaxique).
C’est un arbre dont la racine porte l’étiquette S (axiome de la grammaire). Pour chaque nœud portant l’étiquette X, on construit des fils Y1, Y2, …, Yn si une règle de production de la forme :
X → Y1 Y2 … Yn
a été appliquée.
Le mot dérivé apparaît dans les feuilles de l’arbre en les parcourant de gauche à droite.
Soit la grammaire :
G = ({S}, {a}, S, { S → SS | a })
Pour le mot w = aa :
Pour le mot w = aaa :
Les deux dérivations sont différentes, ce qui montre la possibilité de plusieurs arbres de dérivation pour un même mot.
La dérivation la plus à gauche consiste à remplacer en premier le non terminal le plus à gauche par la partie droite d’une règle de production.
Soit la grammaire :
G = ({Exp}, {(,), id, nb}, Exp, R) avec
R = { Exp → Exp + Exp | id | nb | (Exp) }
Pour le mot :
w = (id + nb) + id
La dérivation la plus à gauche est :
Exp → Exp + Exp → (Exp) + Exp → (id + Exp) + Exp → (id + nb) + Exp → (id + nb) + id
La dérivation la plus à droite consiste à remplacer en premier le non terminal le plus à droite par la partie droite d’une règle de production.
Avec la même grammaire que précédemment, pour le mot :
w = (id + nb) + id
La dérivation la plus à droite est :
Exp → Exp + Exp → Exp + id → (Exp) + id → (Exp + Exp) + id → (Exp + nb) + id → (id + nb) + id
Une grammaire G est dite ambigüe s’il existe pour un même mot au moins deux dérivations la plus à gauche différentes, donc deux arbres de dérivation différents. Sinon, G est dite non ambigüe.
Soit la grammaire :
G = ({A, S}, {a, b}, S, R) avec
R = {
S → aAb | a | abSb,
A → bS
}
Pour le mot abab :
Le mot abab possède deux dérivations la plus à gauche différentes, donc G est ambigüe.
Soit la grammaire :
G = ({S}, {a, b}, S, R) avec
R = { S → SaSaS | bS | ɛ }
Le langage est :
L(G) = { w ∈ {a, b}* | le nombre de a dans w est pair, c’est-à-dire |w|_a = 2k, k ≥ 0 }
Pour le mot baa, il existe deux dérivations la plus à gauche différentes :
Donc G est ambigüe.
Pour cela, il faut d’abord construire un automate fini déterministe reconnaissant L(G), puis convertir cet automate en une grammaire G’ :
G' = ({S, A}, {a, b}, S, R') avec
R' = {
S → aA | bS | ɛ,
A → bA | aS
}