Théorie des languages formels
8 pages
Catalan
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
8 pages
Catalan
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 92
Langue Catalan

Extrait

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

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents