Théorie des langages : Cours theorie des langages langages grammaires
Télécharger PDFChapitre 2 Les grammaires et les langages
Théorie des langages
Partie 1Langages et grammaires
Théorie des langages
Définitions de langages
Si un langage est fini: on peut le définir en énu
mérant tous ces mots. On dit qu’il est défini par extension.
Si un langage est infini: on peut le définir à trav
ers les propriétés de ces mots. On dit qu’il est défini par compréhension. Ce langage peut être décrit par un ensemble de règles qui décrivent la manière de géné
rer ces mots. Chapitre 2 Les grammaires
Théorie des langages
Définition
Exemple1
Soit le vocabulaire V=
{A,B,...,Z,a,b,...,z,0,1,...,9}
A partir de V, on veut définir l’ensemble des ident
ificateurs. Soit L cet ensemble. L ={ident∈ V*/ ident commence par une lettre suivie d’une chaine de chiffres et de lettres éventuellement vide} Théorie des langages
Chapitre 2 Les grammaires
Exemple1 ident
se compose de lettre
concaténée chaine_lettres_chiffres
lettre se compose de a ou
b ou...... ou
z ou
A ou
B ou.... ouZ chaine_lettres_chiffres
se compose de lettre concaténée
chaine_lettres_chiffres
chaine_lettres_chiffres
se compose de chiffre concaténée
chaine_lettres_chiffres
chaine_lettres_chiffres
se compose du mot vide
chiffre se compose de 0ou 1 ou...... ou9 Théorie des langages
Chapitre 2 Les grammaires
Définition
concaténée est remplacée par
. ou
est remplacé par / Exemple1
version 1ident lettre. chaine_lettres_chiffreslettre a/ b/ ........../ z/ A/ B/ ....../ Z
chaine_lettres_chiffres
lettre . chaine_lettres_chiffres
chaine_lettres_chiffreschiffre .
chaine_lettres_chiffres
chaine_lettres_chiffresε chiffre0 /1 /...... /9 Théorie des langages
Chapitre 2 Les grammaires
Définition
Définition formelle
Une grammaire est un quadruplet: G = <VT , VN , S, R>V T
: Vocabulaire terminal (en minuscule): alphabet du langage VN : Vocabulaire non-terminal (en majuscule); (VN ∩ VT = ∅
) S: Axiome ou symbole de départ. S
∈ VN R: Ensemble de règles de la grammaire Théorie des langages
Chapitre 2 Les grammaires
R={ u →
v / u ∈(V TUV N
) +
et v ∈(V TUV N)*} •
Une règle u →
v , u ∈(V TUV N
) +
et v ∈∈∈∈ VT * est appelée règle terminale. •Si plusieurs règles ont la même partie gauche, on peut factoriser leurs parties droites en utilisant ‘|’
S →
ab, S →
aSb, S →c S →
ab|aSb|c
Théorie des langages
Chapitre 2 Les grammaires
Pour l’exemple 1: G1 = <VT , VN , S, R>V T
={A,B,...,Z,a,b,...,z,0,1,...,9}V N
={ IDENT, LETTRE, CHIFFRE, CHAINE_LETTRE_CHIFFRE}
S=IDENTR={IDENT
LETTRE CHAINE_LETTRES_CHIFFRESLETTRE a/ b/ ........../ z/ A/ B/ ....../ Z
CHAINE_LETTRES_CHIFFRES
LETTRE CHAINE_LETTRES_CHIFFRES/ CHIFFRE CHAINE_LETTRES_CHIFFRES/ εCHIFFRE 0/ 1/ ....../ 9} Dérivation
Théorie des langages
La notation u ⇒
v est appelée une dérivation et signifie que: v dérive
de u dans la grammaire G
ou bien u est remplacé par v dans la grammaire G.
Chapitre 2 Les grammairesG Étapes de dérivation
Théorie des langages
Soit une grammaire G = < VT , VN , S, R > Soient u ∈V +
et v ∈
V* avec V= VT UVN G permet de dériver v de u en une étape (u ⇒
v) ssi:
u = xu’y (x, y peuvent être vides)v = xv’y (x, v’, y peuvent être vides)u’ →
v’ est une règle de R
Chapitre 2 Les grammaires
G permet de dériver v de u en plusieurs étapes (u ⇒
v) ssi∃ k ≥ 0 et ∃v 0
, . . . , vk ∈ V∗ tels que
u = v0 ,
v = vk vi v
i +1 pour 0 ≤ i < k est une règle de R
Dans le cas général, on écrit: (u ⇒
v) ssi∃ v
i ∈ V∗ i ∈ [0, k[
tels que
u = v0 , v = vk etv i⇒ vi+1 G
* G
* GG Théorie des langages
Soit G = (VT , VN , E, R)V T
= {
a,+, *, (, )
} , VN = {E,T,F }
R : (
) Chapitre 2 Les grammaires
Exemples de dérivation
Exemple de dérivation
Exemple31 23 45 6124 61 3466 Théorie des langages
Mots générés avec une grammaireSoit G = <VT , VN , S, R> Les mots générés par G sont les mots v ∈V T
* qui sont dérivés à partir de l'axiome S donc S⇒ G v
Langage généré par une grammaireUn langage généré par G est l’ensemble des mots v ∈V T
* qui peuvent être dérivés à partir de S:
L(G) = {v ∈V T
* | S ⇒
G v}
Remarque:•Une grammaire définit un seul langage;•Un langage peut être définit par plusieurs grammaires Chapitre 2 Les grammaires* *S a∈ L(G)aaS 1⇒ aa∈ L(G)2* 2aa nS 1⇒ aan ∈L(G) Théorie des langages
Exemple4G=(VT , VN , S, R)V T
= {a},V N
= {S,S1 }, R : (S aS 1
, S1 aS1 , S
1 ε)
Chapitre 2 Les grammairesL(G)={w ∈V T
* | w=aan n≥ 0}={w ∈V T
* | w=a
n n≥ 1}S aS1 13 33 12 32 ∉L(G) SaS ⇒aa ∈L(G’) 1*2 an S∉ L(G)⇒ an ∈L(G’) Théorie des langages
Exemple5G’=(VT , VN , S, R)V T
= {a},V N
= {S}, R : (S
aS, S
a )
Chapitre 2 Les grammaires
L(G’)={w∈ VT * | w=a
n n≥ 1}S a∈ L(G’)2 22 12 1
L(G)=L(G’)
G et G’ sont équivalentes Théorie des langages
Soit VT = {a,b} et soit L1 =
Chapitre 2 Les grammaires
Exemple5
Trouver une grammaire G1 qui génère L1 { (ab)
n am , n≥ 0, m≥ 0 }
Soit VT ={a,b} et soitL 2
={ (ab)
n am , n≥ 0, m <=n }
Exemple6
Trouver une grammaire G2 qui génère L2 Théorie des langages
Soit VT = {a,b} et L3 ={ abn a , n≥ 0 }
Chapitre 2 Les grammaires
Exemple7
Trouver une grammaire G3 qui génère L3 Exemple8
Trouver une grammaire G4 qui génère L4 Soit VT = {a,b,c} et L4 ={a
n bn cm , n,m≥ 0}