Informatique théorique 2

Géraud Sénizergues

Description

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

Sujets

• Cours
• informatique
• informatique cours

Informations

• Publié par: Force_IT
• Nombre de lectures: 31
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

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 lR