Théorie des languages formels

Théorie des languages formels

-

Documents
8 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

e※0=w⃟ e=s =r,uesi1,2=⃟1 ⃟=i t=,},…l h, den e{ ,,}n i=g{efb h,no dl Contenu Langages ?Contenu Langages ?• Théorie des langages formels • Langages naturels = moyen de communication entre humains• Langages naturels VS langages formels• Définitions, propriétés et opérations sur les langages • Caractéristiques: très riches et complexes, ambigus⇒ traitement difficilement automatisable• Génération VS reconnaissance • Ex: le français « j’aime le langage Pascal. »• Hiérarchie de Chomsky• Langages formels = moyen de communication • Langages réguliershomme-machine ou machine-machine• Définitions et propriétés• Caractéristiques: très réglementés, non-ambigus• Trois représentations: grammaires régulières, expressions ⇒ traitement automatisablerégulières, automates à états finis• Ex: Pascal « res:=x*x*x; if (x>=0) then return res>=0 • Manipulation: déterminisation, minimisation, changement else return res<0»de représentation• Décider si un langage est régulier6 7Théorie des langages formelsCCoommmmuunniiccaattiioonn HHoommmmee--MMaacchhiinnee UUttiilliittéé• Compilation / interprétation de langages de programmation• Information machine = courants électriques• Traitement automatique du langage naturel• Abstraction 1: langage binaire • Conception / vérification de circuits numériques• 0 = pas de courant (ou courant négatif) • Recherche de motifs dans des textes, bases de données, sites web, …• 1 ...

Sujets

Informations

Publié par
Nombre de lectures 129
Langue Catalan
Signaler un problème

Contenu Langages ?Contenu Langages ?
• Théorie des langages formels • Langages naturels = moyen de communication entre
humains• Langages naturels VS langages formels
• Définitions, propriétés et opérations sur les langages • Caractéristiques: très riches et complexes, ambigus
⇒ traitement difficilement automatisable• Génération VS reconnaissance
• Ex: le français « j’aime le langage Pascal. »• Hiérarchie de Chomsky
• Langages formels = moyen de communication • Langages réguliers
homme-machine ou machine-machine• Définitions et propriétés
• Caractéristiques: très réglementés, non-ambigus• Trois représentations: grammaires régulières, expressions
⇒ traitement automatisablerégulières, automates à états finis
• Ex: Pascal « res:=x*x*x; if (x>=0) then return res>=0 • Manipulation: déterminisation, minimisation, changement
else return res<0»de représentation
• Décider si un langage est régulier
6 7Théorie des langages formels
CCoommmmuunniiccaattiioonn HHoommmmee--MMaacchhiinnee UUttiilliittéé
• Compilation / interprétation de langages de programmation• Information machine = courants électriques
• Traitement automatique du langage naturel
• Abstraction 1: langage binaire • Conception / vérification de circuits numériques
• 0 = pas de courant (ou courant négatif) • Recherche de motifs dans des textes, bases de données,
sites web, …• 1 = courant (ou courant positif)
• Preuves de programmes
Ex: 01110000100100100 • Codage / cryptage pour la transmission de données
• Abstraction 2: instructions du microprocesseur • Décodage du génome
• Compression de données• Ensemble des opérations atomiques du processeur
• …(manipulation mémoire, opérations arithmétiques, …)
Mais aussi, liens avec les théories :Ex: MOVE.B #$F0, $FF9001 SUB.B #$1, D0
• de la logique formelle (formalisation du raisonnement)
• Abstraction 3: langages de programmation • de la calculabilité (limites de l’informatique)
• Langage indépendant de la machine • de la complexité (efficacité de l’informatique)
• …Ex: if (x>3) then x:=x-3 else x:=x+3
Théorie des langages formels 8 Théorie des langages formels 9
LLeettttrree,, aallpphhaabbeett,, mmoott IInntteerrpprrééttaattiioonn
• Lettre = symbole !!! ATTENTION !!!
Notation: x, y et z (x , x , …, y , y , …, z , z , …) Ne pas confondre symbole et signification !1 2 1 2 1 2
Ex: ‘a’ ‘2’ ‘begin’ ‘♣’
Note: les ‘’ autour des symboles seront omises en général
Ex: Le (concept du) nombre 4 peut être représenté par les
• Alphabet = ensemble fini de lettres symboles ‘4’, ‘IV’, ou encore ‘ ’.
Notation:Σ, V (Σ , Σ , …, V , V , …)1 2 1 2
Ex: Σ {a,b,c,…,z} Σ Σ {1,2,3,4, } Réciproquement, le symbole ‘4’ peut représenter plusieurs
eΣ concepts : le nombre 4, la lettre d de l’alphabet, le 4
• Mot = suite finie de lettres sur un alphabet élément d’un ensemble, …
Notation: u, v et w (u , u , …, v , v , …, w , w , …)1 2 1 2 1 2
Ex: w= 011001 sur Σ {0,1}
Une lettre n’est qu’un symbole auquel on peut associer w= jaimepascal sur Σ {a,b,c,…,z}
différentes significationsw= 134 Σ {1,2,3,4, }
10 11Théorie des langages formels Théorie des langages formels
1
{ enn,he,b, d }i※⃟=g ,=, {e}n=,f le,l ⃟i2t1 sou r= =s0=1 =e⃟, iwh …edInterprétation Syntaxe, sémantiqueInterprétation Syntaxe, sémantique
• Par définition, mot = suite de symboles; • On distingue deux niveaux pour l’analyse d’un mot :
symboles sans signification => mots sans • Le niveau structurel ou syntaxique définit les mots bien
signification formés (c-a-d., vérifiant des règles de « construction »)
indépendamment de toute interprétation• Donner du sens aux symboles, c’est appliquer une
interprétation
Ex: Soit les mots sur Σ= {1,2,3,4, } Ex: Soit les mots sur Σ= {1,2,3,4, } contenant exactement
• Interprétation 1: 1, 2, 3 et 4 sont les chiffres et est la une fois le symbole
relation « est plus petit que ». 4 3 2 n’est pas bien formé
Ex: 4 3 2 signifie « quatre est plus petit que trois est plus petit que deux » 134 21 et 12 34 sont bien formés134 21 signifie « cent trente-quatre est plus petit que vingt et un»
• Interprétation 2: 1, 2, 3 et 4 sont toujours les chiffres, mais
est la virgule.
Ex: 4 3 2 signifie « quatre virgule trois virgule deux »
134 21 signifie « cent trente-quatre virgule vingt et un »
12 13Théorie des langages formels Théorie des langages formels
SSyynnttaaxxee,, sséémmaannttiiqquuee SSyynnttaaxxee,, sséémmaannttiiqquuee
• On distingue deux niveaux pour l’analyse d’un mot : • On distingue deux niveaux pour l’analyse d’un mot :
• Le niveau structurel ou syntaxique définit les mots bien • Le niveau structurel ou syntaxique définit les mots bien
formés (c-a-d., vérifiant des règles de « construction ») formés (c-a-d., vérifiant des règles de « construction »)
indépendamment de toute interprétation indépendamment de toute interprétation
• Le niveau sémantique définit la valeur d’un mot • Le niveau sémantique définit la signification d’un mot
relativement à une interprétation relativement à une interprétation
Ex: Soit les mots sur Σ = {1,2,3,4, } contenant exactement
Dans ce cours, on ne une fois le symbole , et l’interprétation 1 présentée avant
(1,2,3,4 = chiffres, = « est plus petit que »)
parlera que de syntaxe !134 21 ne reflète pas la réalité
12 34 reflète la réalité
Théorie des langages formels 14 Théorie des langages formels 15
DDééffiinniittiioonnss ssuurr lleess mmoottss OOppéérraattiioonnss ssuurr lleess mmoottss
• Le mot vide (notéε) est le mot constitué de 0 lettres • La concaténation de deux mots v et w (notée v.w)
est le mot constitué des symboles de v suivis de Note: il est donc indépendant de tout alphabet
ceux de w
• L’ensemble de tous les mots finis sur Σ est notéΣ* Note: pour simplifier, on omet le ‘.’ en général
Ex: Σ= {0,1} Σ*= {ε,0,1,00,01,10,11,000,001,…} Ex: v= 011 w= 100 v.w= 011100
v= jaime w= pascal v.w= jaimepascal
• L’ensemble de tous les mots finis d’au moins une • Le mot vide ε est neutre pour la concaténation
+lettre sur Σ est notéΣΣΣΣ • pour tout mot w, w.ε = ε.w = w
+Note:Σ*= Σ ∪ {ε} • Théorème d’unicité de la décomposition:
+Ex: Σ= {0,1} Σ = {0,1,00,01,10,11,000,001,…} • ∀w∈Σ*, ∃! (x , x , …, x ) tq x∈Σ et w= x .x . ….x1 2 n i 1 2 n
⇒ On ne peut pas toujours omettre le ‘.’
Ex: sur Σ={a,b,ab}, quelle est la décomposition de « ab » ?
16 17Théorie des langages formels Théorie des langages formels
2
⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟⃟Opérations sur les mots Opérations sur les motsOpérations sur les mots Opérations sur les mots
ième n• La puissance n de w (notée w ) est un mot v tel • L’ensemble des mots de longueur n sur l’alphabet Σ
nque v=w.w.w. … .w (n fois) est notéΣ
0 1 n n + n 0 1Notes: ∀w∈Σ*, w =ε et w =w ∀n∈N, w =ε⇒ w=ε Note: Σ* = U Σ Σ = U Σ ∀Σ, Σ ={ε} et Σ =Σn∈N n∈N*
0 1 2 0 1 2Ex: sur Σ={a,b} w=aab⇒ w =ε, w =aab, w =aabaab, … Ex: Σ={0,1} => Σ ={ε}, Σ = {0,1}, Σ = {00,01,10,11},
3Σ = {000,001, 010,011,100,101,110,111}, …
• La longueur de w (notée |w|) est le nombre de
ème• Le i symbole d’un mot w est noté w(i)lettres de w
Ex: sur Σ {a,b,c,…,z} w=jaimepascalNote: |ε|=0 ∀w∈Σ*, |w|=0 => w=ε
w(2)=a w(5)=e w(8)=sEx: sur Σ {0,1} |0|= |1|= 1 |011001| = 6
surΣ {00,01,10,11} |011001| = 3
car 011001 = 01.10.01 sur cet alphabet
18 19Théorie des langages formels Théorie des langages formels
OOppéérraattiioonnss ssuurr lleess mmoottss RReellaattiioonnss ssuurr lleess mmoottss
• Une occurrence de la lettre x dans le mot w (notée Soient v et w deux mots:
occ(x,w)) est un entier i>0 tel que w(i)=x Σ*
+Ex: occ(i,jaimepascal)= 3 Σ
occ(a,jaimepascal)= 2 ou 7 ou 10
• Le nombre d’occurrences de la lettre x dans le mot Σ*
+w est noté |w| Σx
Ex: |jaimepascal| =1 |jaimepascal| =3m a
|011100| =3 |011100| =30 1
Théorie des langages formels 20 Théorie des langages formels 21
RReellaattiioonnss ssuurr lleess mmoottss RReellaattiioonnss ssuurr lleess mmoottss
Deux relations d’ordre usuelles:Soient v et w deux mots:
• Ordre préfixe (noté < ):Σ*, Σ* p
Σ*, Σ*, u < u ssi u est un préfixe de u1 p 2 1 2
Note: < est un ordre partiel, c-a-d. certains mots de Σ* ne p
sont pas en relation pour cet ordre
Ex: sur Σ={a,b} aa< aaaabp
mais baa et abb sont incomparables
• Ordre lexicographique (noté < ):L
Σ*, Σ*, u < u ssi u =v.x.w , u =v.y.w et x< y pour 1 L 2 1 1 2 2 Σ
un ordre total < défini sur l’alphabet ΣΣ
Note: < est un ordre total, c-a-d. tous les mots de Σ* sont en L
relation pour cet ordre
Ex: sur Σ={a,b} avec a< b aa< aaaab et abb< baaΣ L L
22 23Théorie des langages formels Théorie des langages formels
3
vs td el e cmrosti iwxw=w wpm m∃m∈m>=q,r éwu=pxenm.= i…x.fxu2 .uxe1eEixa:eww= jeari mpeep axs ceajlsw=m:= l∈awcrsua peexmpifatj.•eLsei fmfouts vp=cxj1v.vxt2 .o e…x.pxpnf(px iu∈lΣs)x xeéspti =uani usaopuasls=oEu.suseo∃ussespo ufse-r-x-u-pm oftemroxtumuoet=m o t∈diuw emfoxtu iwu ss∈sfin sw•=su=0l.axi1w.jux1u.exl2u.su 2r.p i…p. xino.euenraxvéepcp nusiw∈vΣq*tE x :dvf=fjfafiémpapluws=•j=agipmmeap=a>slccaaleei j)wΣa∈sivxx(wnvxu.e…q l.t2ux .s1 x =dwr otpoemi fusdrroipoeriifms reogpaemiif’sLr•olpaeci=f2sun tse mwivauje=q1lut u s> = ldaxcfsuaepiefmsixafj•=1wusea2pxef=uv :uxtEewv=l2cua.evu.=1aus∈p2mua∃=∈m1au=∃: Ei=s.s uw ee∈d∃riusewteceapfrr uxeftrcoapfermue•pur1 ∈xeftrcoup2e∈iaéférrurertrc auft envu= .t auo ev∈•∃riismw eeegiaemiieriieoiréiémr rergrarmni rtieovr i m = sefiUn point de vue ensembliste Opérations ensemblistesUn point de vue ensembliste Opérations ensemblistes
Soient L et L des langages de Σ• Langage = ensemble (fini ou infini) de mots sur un 1 2
alphabet • Union: L Σ1
Note: un langage est une partie de Σ*; l’ensemble des
∅ ∅ ∅langages est l’ensemble des parties de Σ* (notéP(Σ*))
Ex: le langage des nombres binaires sur Σ {0,1}
,a,b,aa,bb, …}le langage des mots du dictionnaire français sur
Σ {a,b,c,…,z}
le langage des programmes en Pascal sur Σ {if, Σ
then, else, while, do, begin, end, …}
∅ ∅ ∅ ∅• Le langage vide (noté Ø) est constitué de 0 mots
Note: Le langage vide est défini sur tout alphabet Σ
Ø (langage vide) { } (langage réduit au mot vide)
}
24 25Théorie des langages formels Théorie des langages formels
OOppéérraattiioonnss eennsseemmbblliisstteess UUnn ppooiinntt ddee vvuuee aallggéébbrriissttee
Soient L et L des langages de Σ • (E, ⊗) est un monoïde ssi :1 2
Σ Σ • E ≠∅
∅ Σ • ⊗ est une loi de composition interne (∀e ,e ∈E, 1 2
Σ Σ (e ⊗e )∈E) et associative1 2
Note: monoïde = semi-groupe
Σ
• (E, ⊗, λ) est un monoïde libre ssi :

• (E, ⊗) est un monoïdeΣ
• λ∈ E
• λ est l’élément neutre pour ⊗ (∀e∈E, e⊗λ = λ⊗e = e)
a,aa,aaa,…} Ex: l’ensemble N des entiers naturels muni de l’addition est
un monoïde libre dont l’élément neutre est 0
Théorie des langages formels 26 Théorie des langages formels 27
UUnn ppooiinntt ddee vvuuee aallggéébbrriissttee UUnn ppooiinntt ddee vvuuee aallggéébbrriissttee
• (E, ⊗) est le monoïde engendré par l’ensemble • Théorème : (Σ ε
nB⊆E ssi∀e∈E, ∃(b , b , …, b )∈B tel que Σ1 2 n
e=b ⊗b ⊗…⊗b1 2 n
Note: il se peut très bien que b=b pour des i≠j donnési j • Σ ε∈Σ
Ex: (N,+) est engendré par {0,1}
∈Σ
• (E’, ⊗, λ) est un sous-monoïde de (E, ⊗, λ) ssi :
n∀ ∈Σ ∃ ∈Σ tel que w=x .x . … .x1 2 n• E’⊆ E (théorème de la décomposition unitaire)
• λ∈ E’
• ⊗ est stable pour E’ : ∀e ,e ∈E’, (e ⊗e )∈E’1 2 1 2 • Tout langage est un sous-algèbre de (Σ ε
Ex: (2N,+,0) est un sous-monoïde de (N,+,0)
28 29Théorie des langages formels Théorie des langages formels
4
oaaéLr= at snew e•caneesr,étfafriids Laεlb•:1 Le-t c* o=scε1,L ):tetcbnoe2rwéefxf i de ée nrué rtvséee on,o)iiteaet∈n eemmétl ptmio c rarlr•beacnn etr é|f2foitdL ,aal, brnupotp e h:c ueaegneihiceuia gt.ehrc unawg e,h c∪u(algtàeneisaNéoa*n∪c ai uecqvlips suopent le=q a∩sooe tdleobaesnn-outsrna bdbasCs N,∈ e*wL*a ∩t:etertIi ocr{d,eat…i{o,rbd…e teiooértdoeLtLiaoPrvd àsàoàiàc te•rctauaennt teer toute•n* eelréttuue nl oetrtt•uneunx xt…snel• :LsLentuorNe}e2tLe∉ewt t•et12L ∈Lw| w|2 * ∈ lwv{t t=m2oL -e i1aLc s:aetcenneircésfefni’D•• }∩lLu=nL (unoi crsieanp’ |uwp|n b|o b*t∈awr{s a=ncb}orbitiasrasbaltee :peaor} Luwnti1o∈n , ∈i{n=tLe1r sneicctsie1n •E{t∩e2oEm:dε aeao,=a}, }b-,ε,b{b ,…ba,,},={{x ettclm lomonda iinr 1n-ed2=e i…a,ubmbcε,∪v}t,iaoa,ε.: )eanptmpie i|tw |v t|t m*o∈ we{i a,c}*a {,=sΣ :sx EeLm n=ï ecl)bceLe(g n*r p=rcs:rsueetao*Ne}t1nLn∉vwd |a *s∈*wL{ o=cct1nLt o: *s rnuesn etraisactanieemεénlep mso C’•l:m n* εe{t e=d }a…c,nbabéba,ibnbo,ib*, ε!{(∩1 }2… ,,axa)a’,•aLa=, a , ε∪{ :oxnE’n ouipnruu’nlr urnursu nervuinttueb:ierot}sLiwdut1e∈ e t∈n{e=tLo:p*m≠e=d=i= ,b,s.o r)b-a-n.tu aobsseosrmbla netm ta busuolrob aentta paibusrolr boacnttn tàoààe
monoïde
libre
engendré
par ΣUn point de vue algébriste Opérations algébriquesUn point de vue algébriste Opérations algébriques
• Attention : Il existe des langages qui ne sont pas des Soient L1 et L2 deux langages :
n sous-monoïdes de (Σ ε • Puissance : ∀n∈N, L = {w * | u L , … u L , 1 1 1 n 1
({a,b} ε w=u . … . u }1 n
ε∉ L n 0Note: L = L .L . … .L (n fois) L ={ε}1 1 1 1 1
0 1Ex: sur {aa,ab,ba} => L ={ε}, L ={aa,ab,ba},
2 Soient L1 et L2 deux langages : L = {aaaa,aaab, aaba,abaa,abab,abba,baaa,baab,baba}
• Concaténation : L .L = {w * | u L , v L , w=u.v}1 2 1 2
nNote: Ne pas confondre avec ‘.’ sur les mots • Itération : L * = {w * | n N, w L }1 1
{ε} est neutre pour la concaténation nNote: L* = U Ln∈N
∅ est absorbant pour la concaténation Ex: sur {aa,ab,ba}
Ex: {a,aa,…} . {b,bb, …} = {ab,aab,abb,aabb, …} => L* = {ε aaaa,aaab,aaba,
abaa,abab,abba,baaa,baab,baba, …}
30 31Théorie des langages formels Théorie des langages formels
MMoorrpphhiissmmee MMoorrpphhiissmmee
• Une application h de (E ,⊗) dans (E ,⊕) est un morphisme Soient Σ et Σ des alphabets :1 2 1 2
ssi∀e,e’∈E , h(e⊗e’)=h(e)⊕h(e’)1 • Un morphisme h: (Σ (Σ1 2
Note:
h h
• Morphisme = Homomorphisme
h: ({a,b} ({0,1} h h• Si (E,⊗) = (E’,⊕), alors h est un endomorphisme
-1h : ({0,1} ({a,b} h h• Si λ (resp. λ’) est le neutre de (E,⊗) (resp. (E’,⊕)), alors h(λ)= λ’
Ex: f: (N,+) (N,+) tq f(n)=n+2 est un morphisme
2g: (N,+) (N,+) tq g(n)=n n’est pas un morphisme h: (Σ (Σ ∈Σ *; 2 2 1
2h: (N,*) (N,*) tq h(n)=n est un morphisme l’image de w par h est le mot h(w)=h(x ).h(x ). … .h(x ) ∈Σ *1 2 n 2
Ex: h: ({a,b} ({0,1} h
• Un morphisme h: (E,⊗) (E’,⊕) est un isomorphisme s’il
existe un morphisme inverse
-1 -1 h: (Σ (Σ ⊆Σ *; l’image 1 2 1h : (E’,⊕) (E,⊗) tq∀e∈E, h(h (e))=e
-1 de L par h est le langage h(L)⊆Σ * définit par h(L)={w∈Σ | et ∀e’∈E’, h (h(e’))=e’ 2 2
∃u∈Σ , h(u)=w}Note: Si (E,⊗) = (E’,⊕), alors h est un automorphisme 1
Ex: Dans l’exemple précédent, f est un isomorphisme, pas g ni h Ex: h: ({a,b} ({0,1} ε h ε
32 33
GGéénnéérraattiioonn VVSS RReeccoonnnnaaiissssaannccee GGéénnéérraattiioonn VVSS RReeccoonnnnaaiissssaannccee
• Questions: étant donné un langage L Représentation ensembliste des langages ?
• Génération: comment engendrer tous les mots
appartenant à L ? • Problème: pas manipulable en machine puisque
• Reconnaissance: comment reconnaître qu’un mot w certains langages sont infinis …
donné appartient à L ?
• Réponse: définir un algorithme de génération et un
• Idée: la syntaxe d’un langage est un ensemble de
algorithme de reconnaissance de L
règles de construction => représentons un langage
par ces règles !
• Problème: nombre infini de langages => nombre
infini d’algorithmes ?
C’est le formalisme des grammaires formelles• Idée: utiliser une représentation uniforme des
langages => algorithmes standards
34 35Théorie des langages formels Théorie des langages formels
5
∃0e1N,-1(0c,d0 ,Σbd{.=o)aL (d,∃ } ) i S d}eaa,o éat,s,o.,)r,∈.{)= ee sbtn a.p)p1exlgéxcaoedoaageeocéoedaangu,o.d) . c ∈ ∃ ∃wΣ=,a }Σ∈*L,a a.-,) S) Ecxg: ’ent ,}eb=,xa…{gbc,db:aE,gad,c.g{d=cLg d c g d c)é.é,d)s,pbsau, aoas)m.nnïlene *e ),,){a, .Σb∈,∈LΣ ∈g∈d=canb , Lu∈,∃)∈a e g-g(a= LuitS 0.1==aw),,b}e ,=meiapoo ,u)tsog•a1d0o)c(éadb neus htremm.doai n 1.= )vbc(ta1 0 =,,0s=1)1a=(•lo t uc eovaae e i):.,,)oores. -t1wex)..2, s.tn asooena odedGrammaires formelles Grammaires formellesGrammaires formelles Grammaires formelles
• A un langage L, on associe une grammaire • Pour toute grammaire :
G = (V ,V ,S,R) avec : • ∃α→β∈R tqα=S (règle issue de l’axiome)T N
• V = vocabulaire terminal (= alphabet de L) • V ∩ V = ∅T T N
• V = vocabulaire non-terminal (= symboles intermédiaires N
n’appartenant pas à l’alphabet du langage L) • Conventions de notations:
• S= un symbole particulier de V appelé axiomeN • α représente la partie gauche d’une règle
• R= ensemble de règles α→β avec β∈(V ∪V )* et T N • β représente la partie droite d’une règle
α∈(V ∪V )*.V .(V ∪V )* (au moins un symbole non-T N N T N • S représente l’axiome de toute grammaireterminal)
• Les règles α→β et α→β’ peuvent se noter α→β | β’
• On note L(G) le langage engendré par la grammaire GEx: G =({a,b},{S,A},S,{ S → bA, 1
S → a,
bA→ a})
36 37Théorie des langages formels Théorie des langages formels
GGrraammmmaaiirreess ffoorrmmeelllleess DDéérriivvaattiioonn
• Notation Backus-Naur Form (BNF): • Dérivation directe: Étant donnée une grammaire
G=(V ,V ,S,R), un mot u∈(V ∪V )* se dérive • Tout symbole non-terminal x se note <x> T N T N
directement en un mot v∈(V ∪V )* (noté u • Tout mot w sur l’alphabet terminal V se note "w"T T N
∃u ,u ∈(V ∪V )* α→β∈R tel que u=u .α.u et • Toute règle α→β se note α’ ::= β’ oùα’ et β’ sont les 1 2 T N 1 2
notations BNF de α et β v=u .β.u1 2
Note: on note parfois u Ex: G =({a,b},{S,A},S,{ <S> ::= "b"<A> | "a", 1
"b"<A> ::= "a"})
Ex: par G =({a,b},{S,A},S,{ S→bA | a, bA→a}), 1
aaSba S→a)
Théorie des langages formels 38 Théorie des langages formels 39
DDéérriivvaattiioonn GGéénnéérraattiioonn
• Dérivation: Étant donné une grammaire
∈V * (mot terminal)G=(V ,V ,S,R), un mot u∈(V ∪V )* se dérive en un TT N T N
Ex: pour G =({a,b},{S,A},S,{ S→bA | a, bA→a}), Smot v∈(V ∪V )* (noté u 1T N
∃u ,…,u ∈(V ∪V )* tels que u u1 n T N 1
=(V ,V ,S,R) engendre le langage T N
• Ex: par G =({a,b},{S,A},S,{ S→bA | a, bA→a}), 1 L(G) = {w∈V * | S T
aaS
aaS

aaS

40 41Théorie des langages formels Théorie des langages formels
6
(diiuree}c*t>ee)Snaovi t⊦arvti rSé d (1aha a⊦⊦qa = e=f i : b ,)⊦ebtc*ls naé’a n* vm⊦raaead ro(re a a bétiΣL{r,a} caraS=a es ⊦⊦}Aoaeoutuldsndoun betéEé1aai,nA ,d iAe,n⊦édéiéeénrea(t=i o nl:vr*a tvi*o n⊦:⊦r altriuoinn: ruaptvi⊦oane:tuuneeg ndrétroi•vaagtaimoine Gceridni noitaviréd(aaa⊦Abaa⊦ub⊦a*ava ⊦ers⊦tt iusn⊦e* wg=é nnérrtaotvi onn ésisiii nue=sSm l(sle’!axxGi=o{m,e}){ ,e}tS {v *b⊦|va⊦ Anau)⊦é⊦r⊦t⊦l… …a…g…g⊦s⊦L⊦G⊦)⊦{⊦}⊦s⊦rilsasp a)er è=galbe éas i⊦l ittSvbv⊦v sun eev )e xuse l•sGgGnGrGtéoéséaémnsnsnArbre de dérivation AmbiguïtéArbre de dérivation Ambiguïté
• Génération Arbre de dérivation : • Une grammaire est ambiguë ssi il existe au moins 2
générations distinctes pour un même mot• Axiome racine de l’arbre
• Symboles (V ∪V ) nœuds de l’arbre Ex: →T N
→• Application d’une règle α→β α∈V et β=x x …xN 1 2 n
avec ∈ ∪
arcs (α,x ), (α,x ), …, (α,x ), de l’arbre1 2 n
Ex: Soit G=({a,b},{S,A},S,{S→ b | bS | bA,
• Une grammaire G est non-ambiguë ssi tout mot w A→ a | aA})
S appartenant à L(G) admet une unique génération
b S S
S b A
a
42 43Langages réguliers
Génération VS Reconnaissance (round 2)Génération VS Reconnaissance (round 2) HHiiéérraarrcchhiiee ddee CChhoommsskkyy
• Utiliser les grammaires ? • Une grammaire G=(V ,V ,S,R) est de type:T N
+• Génération: utiliser mécaniquement les règles pour • 3 ssi∀α→β∈R, α∈V et β∈ (V *.V )∪VN T N T
produire toutes les générations
+• 2 ssi∀α→β∈R, α∈V , β∈(V ∪V )N T N
+• 1 ssi∀α→β∈R, α,β∈(V ∪V ) et |α| ≤ |β|T N
• 0 sinon
Problème: dérivations infinies possibles !
Ex: G =({a,b},{S,A},S,{S→A, A→S}) donne la dérivation 3 • Exception: la règle S→ε est autorisée dans les
infinie S S grammaires de types 1, 2 et 3 ssi S n’apparaît
jamais en partie droite (β)
• Inclusion:∀j<i, G de type i ⇒ G de type j
Théorie des langages formels 44 Théorie des langages formels 45
CCllaassssiiffiiccaattiioonn ddee ggrraammmmaaiirreess HHiiéérraarrcchhiiee ddee CChhoommsskkyy
• Classification = déterminer le type d’une grammaire • Classification des langages :
• Inclusion essayer le type le plus haut en premier Un langage est de type i ssi il est engendré par une
Ex: la grammaire G =({a,b},{S,A},S,{ S → bA | a, grammaire de type i et par aucune grammaire de type j > i1
bA → a})
• n’est pas de type 3 car la règle bA→a ne vérifie pas
• Dénomination des langages :bA∈VN
• Type 0 = langages quelconques• n’est pas de type 2 pour la même raison
• Type 1 = langages contextuels• n’est pas de type 1 car la règle bA→a ne vérifie pas
|bA|≤|a| • Type 2 = langages hors-contextes (ou algébriques)
• est donc de type 0 • Type 3 = langages réguliers (ou rationnels)
Ex: la grammaire G = ({a,b},{S},S,{S → a})2
+• est de type 3 car sa seule règle vérifie S∈V et a∈VN T
Et pourtant G1 et G2 reconnaissent le langage {a}
46 47Théorie des langages formels Théorie des langages formels
7
’ncnAaAiSsbssaunic*ea:⊦ReeRcaoen ntaSi,s,s1abnVcnec:ngcéengéurteeré jtu sAq u,’Sàbt(raoAuSvVexovri ol:ea amco t }àtrbeëcso nmn‘adî téraen⊦iAn⊦s⊦⊦At⊦⊦…a=w>{ Sd}é,t{e}c,t{e=rG bc⊦ebs⊦ bgNéTnié reaatsiaonncsR e=n scianroaec•taeR:ecnasé,rbias)esr mlieusp igqrealm moa iaraemst 2egtn rlteoss dlsaincgea g ease| A bb ⊦ ⊦ SGGéénnéérraattiioonn VVSS RReeccoonnnnaaiissssaannccee ((rroouunndd 33))
• Pour certaines classes de langages, on dispose
d’autres formalismes de représentation qui
permettent de répondre plus simplement aux
problèmes de génération et de reconnaissance.
• C’est le cas des langages réguliers qui peuvent être
représentés par :
• Grammaires régulières (type 3)
• Expressions régulières
• Automates à états finis
48Théorie des langages formels
8