Théorie des langages
suite chapitre III
Les grammaires régulières
Sajeh ZAIRI CHIHI
École Supérieure d’Économie Numérique - Manouba
23/04/2015
1
Dérivation
• 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 chaine u par la
sous chaine v
23/04/2015
2
Langage généré par une
grammaire
• Soit G = (V,T,S,R) une grammaire
L(G) est le langage généré par la G, c’est
l’ensemble des mots dérivés à partir de S
L(G) = {W ∈ T / S w}
23/04/2015
3
23/04/2015
Grammaire non
contextuelle (hors contexte)
• 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) tel que R ={S aSb|ɛ}
4
23/04/2015
Grammaire dépendante du
contexte
• 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) tel que
R ={S AB, A aAb|ɛ, B cB|ɛ}
Publicité
L(G) = {w ∈ {a,b}* / w= anbn cm, n>=0, m>=0}
5
23/04/2015
Langage indépendant du
contexte
• Un langage est dit indépendant du contexte s’il
existe une grammaire non contextuelle qui le
génère
ab ∈ {Langages Réguliers}
{anbn , n>=0} ∈ {Langages Indépendants du Contexte}
{anbn cm, n>=0, m>=0} ∈ {Langages Dépendants du
Contexte}
6
23/04/2015
Arbre de dérivation
• A chaque dérivation d’un mot à partir d’une
grammaire est associée un arbre appelé arbre de
dérivation (ou arbre syntaxique)
• C’est un arbre qui admet comme racine un nœud
portant comme étiquette S (axiome de la
grammaire) et pour chaque nœud portant
comme étiquette X, on construit des fils
Y1, Y2, …, Yn si une règle de production de la
forme X Y1Y2…Yn a été appliquée
• Le mot dérivé apparait dans les feuilles de l’arbre
en les parcourant de gauche à droite
7
Exemple d’arbre de
dérivation
G = ({S},{a},S,{S SS|a})
Soit w=aa
• Dérivation 1
S SS aS aa
• Dérivation 2
S SS
Sa aa
23/04/2015
8
Exemple d’arbre de
dérivation
G = ({S},{a},S,{S SS|a})
Soit w=aaa
• Dérivation 1
S SS aS aSS aaS
aaa
23/04/2015
Publicité
9
23/04/2015
Exemple d’arbre de
dérivation
G = ({S},{a},S,{S SS|a})
Soit w=aaa
aaa
• Dérivation 2
S SS
aaa
SSS SSa Saa
Dérivaon1 ≠ Dérivaon2
10
23/04/2015
Dérivation la plus à gauche
• C’est une dérivation où c’est le non terminal le
plus à gauche qui est remplacé le premier par
une partie droite d’une règle de production
Exemple
G = ({Exp},{(,),id,nb},Exp,R) tq
Exp + Exp|id|nb|(Exp)})
R = {Exp
w = (id+nb)+id
Exp + Exp
Exp
(id + Exp) + Exp
(Exp) + Exp
(id + nb) + Exp (id + nb) + id
(Exp + Exp) + Exp
11
23/04/2015
Dérivation la plus à droite
• C’est une dérivation où c’est le non terminal le
plus à droite qui est remplacé le premier par
une partie droite d’une règle de production
Exemple
G = ({Exp},{(,),id,nb},Exp,R) tq
Exp + Exp|id|nb|(Exp)})
R = {Exp
w = (id+nb)+id
Exp + Exp
Exp
(Exp + Exp) + id (Exp + nb) + id (id + nb) + id
Exp + id (Exp) + id
12
23/04/2015
Publicité
Grammaire ambigüe
• 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 arbre
de dérivation différentes)
• Sinon G est dite non ambigüe
13
Exemple de grammaire
ambigüe
• G = ({A,S},{a,b},S,R) tq
R = {S aAb|a|abSb, A bS)
• Dérivation 1
S aAb
abSb abab
• Dérivation 2
S
abSb abab
• Le mot abab a deux dérivations
la plus à gauche différentes
donc G est ambigüe
23/04/2015
14
Exercice
Soit G = ({S},{a,b},S,R) tq R = {S SaSaS|bS|ɛ}
1. Quel est le langage ?
L(G) = {w ∈ {a,b}* / |w|a= 2k, k>=0}
2. Montrer que G est ambigüe ?
w=abb
dlpg1 : S SaSaS bSaSaS baSaS baaS
baa
dlpg2 : S bS bSaSaS baSaS baaS
baa
23/04/2015
15
Exercice (suite)
Pour le mot baa , il existe 2 dlpg à partir de S différente
donc G est ambigüe
3. Construire G’, équivalente à G, non ambigüe
Pour commencer il faut construite un automate fini
déterministe reconnaissance L(G)
Ensuite convertir l’automate en une grammaire
G’ = ({S},{a,b},S,R’) tq R = {S aA|bS|ɛ, A bA|aS}
23/04/2015
16