Informatique théorique 2

Informatique théorique 2

-

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

Description

Document sur la théorie des Langages Formels ; explication du mécanisme et des mots.

Sujets

Informations

Publié par
Nombre de lectures 31
Langue Français
Signaler un problème

Informatiqueth´eorique2
notes de cours

Ge´raudS´enizergues

1
Anne´e20102011

1
derni`eremise`ajour:29mars2011

2

Tabledesmati`eres

1 Langagesrationnels de mots9
1.1Mots,monoı¨des..........................9
1.2 Automatesfinis . . . . . . . . . . . . . . . . . . . . . . . . . .11
1.3Lemmed’ite´ration........................15
1.4Proprie´t´esdeclˆoture.......................17
1.5 Automateminimal .. . . . . . . . . . . . . . . . . . . . . . .21
1.6 Expressionsrationnelles .. . . . . . . . . . . . . . . . . . . .31

2Langagesalge´briquesdemots35
2.1Arbresplanairesordonn´es....................35
2.2Grammairesalg´ebriques.....................36
2.3Arbresded´erivation.......................42
2.4Formesnormalespourlesgrammairesalge´briques.......45
2.5Lemmed’it´eration........................54
2.6Propri´et´esdecloˆture.......................55
2.7Automatesa`pile.........................60

3 Langagesrationnels de termes67
3.1Termes,Falge`bres........................67
3.2 Automatesfinis . . . . . . . . . . . . . . . . . . . . . . . . . .72
3.3Lemmed’it´eration........................75
3.4Propri´ete´sdecloˆture.......................78
3.5 Automateminimal .. . . . . . . . . . . . . . . . . . . . . . .86
3.6 Expressionsrationnelles .. . . . . . . . . . . . . . . . . . . .89

4 LogiqueMonadique du Second Ordre93
4.1Syntaxeetse´mantique......................93
4.2Ensemblesdemotsde´finissablesenMSO............97
4.3 Ensemblesde termes definissables en MSO .. . . . . . . . . . 102
3

4

`
TABLE DES MATIERES

5Langagesre´cursivemente´num´erablesdemots105
5.1 Grammairescontextuelles .. . . . . . . . . . . . . . . . . . . 105
5.2Grammairesa`structuredephrase...............107
5.3Hie´rarchiedeChomsky......................112
5.4Unprobl`eme...........................113

Introduction

Quevatone´tudier?d’InformatiqueTh´eorique2etLroamiutdeel
delath´eoriedesLangages Formels. Le mot “langages” est certainement
connudulecteur;l’´epithe`te“formels”pre´cisequenouse´tudionslesmots
des langages du point de vue de leur “forme” et non de ce qu’ils pourraient
e´voquer`aunlocuteurdecelangage.Cettenotiondeformes’oppose`acelle
du “ sens” des mots et des phrases, qui est certes essentielle, et fait l’objet
dela“se´mantique”deslangages.Onseconcentreicisurlaforme,nonpar
me´prisdusens(cequiseraitabsurde),maisparcequenousappliquonsune
strat´egie“diviserpourre´gner”dansledomainedel’´etudedeslangages:
cettede´marches’ave`resouventefficacetantpourlechercheurquepourle
p´edagogueetl’´etudiant.Enfait,ons’apercevraencoursderoutequ’une
bonnecompr´ehensiondelaformefournitdesoutilspertinentspouressayer
dede´duirelesens(desmots,desphrases,dudiscours)del’analysedeleur
forme.

Pourquoi ?emenriquuxgrt,deps´rnaedputaoeccnsiotconduon`aitotsiH
s’inte´resserauxlangagesformels.

P1Lesmath´ematiciensdelasecondemoiti´edu19ie`mesi`ecleontcherch´e
(etr´eussi)`adonnerauxmath´ematiquesuneformeplusrigoureuse,donc
soulevantmoinsdecontroverses;lacl´edecetterigueurestlade´finitiond’un
langage artificiel, beaucoup plus pauvre que la langue naturelle (au moyen
delaquelleon´ecrivaitlesmathe´matiques`acettee´poque)mais,enrevanche,
de´finiedefac¸onbeaucouppluspr´ecise.Nousappelleronscelangagela“
languemathe´matiqueformelle”.Enparticulier,onpeutais´ementve´rifiersi
un´enonce´pre´tenduˆmente´critdanscettelangueesteffectivementun´enonc´e
5

6

`
TABLE DES MATIERES

correctementforme´decettelangue.Onpeut´egalementv´erifier,enprincipe
dumoins,siunesuited’e´nonce´s(correctementforme´s)estre´ellementune
d´emonstration.notiquedonn´ee,oundnausenxaoiam

P2Depuisle18i`emesi`ecleaumoins,leslinguistess’efforcentdede´crire
leslanguesnaturelles.Aude´butdu20i`emesi`ecle,ilssesontpre´occup´es
d’inventer desuqitame´seleseamhtom`dugselsna.rueled’´tdjeoblee:udet
AinsilesABgrammaires,apparuesdanslesanne´es1930d´ecriventcertaines
phrasessimplesdeslanguesnaturelles.Lesgrammairesalge´briques(quisont
apparuesdanslesanne´es1950etquenouse´tudieronsici),lesgrammaires
cate´gorielles(quidatentdelamˆeme´epoque)sontdes´evolutionsdesAB
grammaires.Depuislors,denombreuxautresmode`lesontvulejouret
continuenta`eˆtreinvent´esouperfectionn´esparlessp´ecialistesdelinguistique
computationnelle.

Unefoislathe´orielance´eparcesdeuxmotivations,desliensfructueux(et
prometteurs,carrienn’esttermin´e)sontapparusaveclesdomainessui
vants :

– la conception des Langages de Programmation : i.e. la construction de
langues artificielles qui permettent d’exprimer des calculs ; de tels langages
doiventˆetresuffisammentrichespoursatisfairelesd´esirsdesutilisateurs
(quisouhaitentr´ealiserdescalculscomplique´s)etdoiventaussipouvoir
ˆetrecomprisdesordinateurs,dontlelangagenatif,le“langagemachine”,
esttre`sprimitif.Latraductiondesprogrammes´evolue´sversleslangages
machine est l’objet de lacompilation;
–laTh´eoriedesmod`eles:i.e.l’e´tudedesstructuresensemblistesquirendent
vraie (ou fausse) une formule logique ou un ensemble de formules logiques ;
cesujetestabord´e`alasection4.
–LaThe´oriedelacomplexit´edesalgorithmes:unalgorithmepeuteˆtre
d´efinicommeunemachineoubienunprogrammed’unemachine;on
d´efinitalorsunenotiondecomplexite´lie´eautypedemachinesutilis´e.La
notioninformellementutilise´edanslesenseignementsd’ASDestsouvent
celleassoci´eeauxmachinesdites“R.A.M.”(RandomAccessMemory
machines).
–LaThe´oriedesJeux:initialementils’agissaitdemod´eliserlecomporte
mentdesacteursd’une´economiedemarch´e;ils’av`erequelesconcepts
cle´sdecetteth´eorie(notiondestrat´egiegagnante,dejeud´etermin´e)sont
tr`espertinentspourtraiterdeproble`mesd’automates.

`
TABLE DES MATIERES

7

–l’Alg`ebre:ils’agiticidel’´etudedesstructurestellesquelesgroupes,
lessemigroupes,lesmonoı¨des,etc...Lanotiondelangagerationnelest
tre`slie´e`acelledemonoı¨definiparexemple;deslienssubtilsentreles
expressionsrationnellesetlesmono¨ıdesconduisenta`desalgorithmesque
l’onauraitdumala`concevoirdirectementsurlesautomatesfinis.
–LaCombinatoire:c’estl’art(etlascience)dude´nombrementsd’objets
discretsde´finisparleurspropri´ete´soubienpardesr´ecurrences.Ils’ave`re
quelesre´currencesd’uncoˆt´e,etlesgrammaires,del’autre,sontsouvent
tr`eslie´es.
–LaBiologiemol´eculaire:unemole´culed’ADN(oud’ARN)estsouvent
mode´lis´eecommeunmotsurunalphabetdequatrelettres(A,C,D,G).
Ils’agitdemotstr`eslongsetlaconceptiond’algorithmesefficacesde
traitementdetellesmol´eculesobtenuesexpe´rimentalementpasseparfois
parlamod´elisationpardesgrammaires,desautomates,dessyst`emesde
r´e´ecritureoud’autressyst`emesformelspluscomplexes.

QuellesautresUEsontconcern´ees?
En “amont” :
L’Unite´d’Enseignementintitule´e“InformatiqueTh´eorique1”fournitles
bases indispensables concernant les automates finis, les expressions ration
nellesetplusg´ene´ralementlesmathe´matiquesdiscr`etes.
L’Algorithmique,qu’ellesoitge´ne´raleetassocie´eaux“StructuresdeDonne´es”,
oubienfocalis´eesurlesGraphes,esttr`esutilepourconcevoirdesalgorithmes
portant sur les langages formels.

En “aval” :
Lesconcepts,propri´ete´setalgorithmesquenousintroduisonsicisont
 essentiels pour les UE d’ Analyse Syntaxique (L3) et de Compilation (M1)
utilespourl’UEdeMode`lesdeCalcul(M1)
 utiles pour l’UE de Logique (M1)
 essentiels pour l’UE de Linguistique Computationnelle (M2)

8

`
TABLE DES MATIERES

Chapitre 1

Langages rationnels de mots

1.1 Mots,mono¨ıdes

D´efinition1.1.1ripletdeestuntnUomonı¨M= (M,∙, e)u`o,Mest un
ensembleM,∙viseitcuteasru´eraneopassotionMeteerse´eel’´tlutnentme
deMpour cette loi.

SoitXun ensemble. Unmotsur l’alphabetXitinu,nopaenstear,pefid´
plication partant d’un intervalle [1, n] deNet arrivant dans l’ensembleX:
u: [1, n]→X.
Lemotparticuliercorrespondanta`l’applicationvideestd´enomme´le“mot
vide”etnote´ǫ.

Onde´noteparX’arlhalptbe,l’mbleenseto´sedmsstusceirX.
Soientu: [1, n]→X, v: [1, m]→Xdeux mots. Lena´eontiporudtiedoccnta
deuparvest le motwobtenu en juxtaposantuetv. Formellement,w=u∙v
estd´efinipar:

dom(w) = [1, n+m],∀i∈[1, n], w[i] =u[i];∀j∈[1, m], w[i+j] =v[j].


Remarquons que, pour toutu∈X
u∙ǫ=ǫ∙u=u.
9

10

CHAPITRE 1.LANGAGES RATIONNELS DE MOTS


D´efinition1.1.2Pour tout alphabetX,(X ,∙, ǫ)lnO.edı¨pa’enomounst
pellele“mono¨ıdelibreengendre´parX”.

De´finition1.1.3SoitM= (M,∙, e). Unı¨edomonusosdeMest un triplet

′ ′
M= (M ,⊙, e)tel que :

–M⊆M

–e=e

′ ′′
–∀m, m∈mM ,⊙m=m∙m.
SiIest un ensemble d’indices et si∀i∈I,Mi= (Mi,∙, e) est un sous
T
lors (∙, e) est un sousmono¨ıde deM.
monoı¨dedeM, ai∈IMi,

De´finition1.1.4SoitYarepunedı¨onomnu’deitM. On appellesous
monoı¨deengendre´parYpel,psultiteussoonmıdo¨eedMcontenantY.

On le noteY.


D’apr`escequipre´ce`de,Yest l’intersection de tous les sousmono¨ıdes de
Mqui contiennentY.

Exemple 1.1.5SoitN= (N,+,0). SoitAl’ensemble des nombres pairs
etBl’ ensemble des nombres impairs.(A,+,0)ededı¨onomsouestlesN
engendre´par{2}tandis que(B,+,0)edıden’essaptosnumsu¨onoN.

′ ′′
D´efinition1.1.6SoientM= (M,∙, e),M= (M ,×, e)nomsed.sedı¨o

On appellehomomorphisme( de mono¨ıde) allant deMdansM, toute

applicationhdeMdansMverifiant :

–h(e) =e
′ ′′
–∀m, m∈ M, h(m∙m) =h(m)×h(m)

Exemple 1.1.7mnua`iuqtoilacitnoLa’ppuassocie sa longueur|u|est un

homomorphisme de(X ,∙, ε)dans(N,+,0).

n
L’applicationn7→2est un homomorphisme de(N,+,0)dans(N,×,1).

Th´eor`eme1.1.8SoitXun alphabet. Soit(M,∙, e)nomountiosteedı¨h
˜
une application deXdansM. Il existe un et un seul homomorphismeh:
˜

X−→Mtel que∀x∈X, h(x) =h(x).