[PDF] Théorie des automates et langages formels

View - Download Théorie des automates et langages formels

Previous PDF

Next PDF

Facultedessciences

Departementdemathematiques

Theoriedesautomates

etlangagesformels 1a c b 2 ad c b 3 a,c,db4 b c a 5 d c a 6 b,c,da7 a,b c 8d c 9 a,b,c,da,b b d dd

Anneeacademique2009{2010

MichelRigo

Tabledesmatieres

ChapitreI.Motsetlangages1

1.Premieresdenitions1

2.Langages10

4.Exercices22

ChapitreII.Automates27

1.Automatesnisdeterministes27

2.Automatesnondeterministes29

4.Produitd'automates43

5.Exercices46

1.Desexpressionsauxautomates51

2.Desautomatesauxexpressionsregulieres54

3.Stabilitedelaregularite57

4.Criteredenon-regularite58

5.Exercices61

ChapitreIV.Automateminimal63

1.Introduction63

2.Congruencesyntaxique64

3.Automateminimal66

4.Constructiondel'automateminimal72

5.Applications77

6.Exercices81

1.Transduction85

2.Recherched'unmotdansuntexte88

4.Monodesyntaxique99

5.Langagessansetoile105

6.Exercices109

1.Premieresdenitions115

i iiChapitre.Tabledesmatieres

2.Arbresd'analyse119

3.Uneillustrationdel'ambiguite122

4.Grammairesetlangagesreguliers126

5.AproposdelahierarchiedeChomsky128

6.Formesnormales130

7.Lemmedelapompe140

8.Automatesapile143

9.Stabiliteducaracterealgebrique151

10.UntheoremedeSchutzenberger152

11.Exercices155

Bibliographie159

Listedesgures161

Index165

CHAPITREI

Motsetlangages

1.Premieresdenitions

Denition

=fa;b;cg;=f~;};|;g;=f0;1g;=f!; ;";#g boles Exem

Adenine,Cytosine,GuanineetThymine.

Denition

constituantcemot;onlanotejwj.Ainsi, jabbacj=5etjbaj=2: note.Parexemple,

Denition

w

1wk2,ondenotepar

jwj=#fi2f1;:::;kgjwi=g

2etjabbacjc=1.

1

2ChapitreI.Motsetlangages

:!Nnpar (w)=(jwj1;:::;jwjn): Len-uple (w)estappelevecteurdeParikhdew.Ilestclairquesin>1, alors n'estpasinjectif.

Denition

I.1.5.Soitw=w1w`unmotsur.Lesmots

";w1;w1w2;:::;w1w`1;w1w`=w

Defaconsemblable,

";w`;w`1w`;:::;w2w`;w1w`=w dewestnotePref(w)(resp.Su(w),Fac(w)). Remar estdenombrable1.

Rappelonsladenitiond'unmonode.

Denition

I.1.7.SoientAunensembleet:AA!Auneopera-

IL'operationestassociative:

8x;y;z2A:(xy)z=x(yz):

IIlexisteunneutre(unique)e2Atelque

8x2A:xe=ex=x:

Remar possedeuninverseestungroupe. Exem n'estpasungroupe. d'ensemblesnis,asavoir).

I.1.Premieresdenitions3

homomorphisme)demonodessi (1)8x;y2A:f(xy)=f(x)rf(y) et (2)f(eA)=eB: Remar

Denition

uv,estlemotOnutilisera dorenavant lanotation multiplicative.w=w1wk+`ouwi=ui;1ik w k+i=vi;1i`: concatenationdencopiesdew, w n=ww| {z} nfois:

Onposew0=".

Remar Exem pleI.1.14.L'applicationlongueur jj:!N

8u;v2:juvj=juj+jvj

etj"j=0. Exem lettres.Ona,parexemple, '(abbc)='(a)'(b)'(b)'(c)=abcacacb: parf(x)1.

4ChapitreI.Motsetlangages

Pro aisee. commun.Six=y,alorsonposed(x;y)=0,sinon d(x;y)=2jx^yj: termenon-archimedienne):

8x;y;z2!:d(x;z)maxfd(x;y);d(y;z)g:

Pro '(c)=b,estsanscarre. unmotinnilimite. isocele,etc.

I.1.Premieresdenitions5

'0(a)=a

1(a)=abc

2(a)=abcacb

3(a)=abcacbabcbac

arbitrairementlongssanschevauchement. Pro u=wietv=wj. uvu v u'

FigureI.1.uv=vu.

v=u0u=wp+q. Remar iale. elleaussiimmediate). Pro positionI.1.20.Six;y;zsontdesmotstelsque xy=yz

6ChapitreI.Motsetlangages

x=uv;y=(uv)ku=u(vu)ketz=vu: yyx zyv

FigureI.2.xy=yz,jxjjyj.

peutprendreu=yetk=0. jxj=jzj=1,ona xy1y2=y1y2z;x;z;y1;y22 xy yz xw

FigureI.3.xy=yz,jxj y=xw.Ainsi,xy=yzsereecrit xxw=xwz: telsque x=uv;w=(uv)ku=u(vu)ketz=vu:

Pourconclure,onremarqueque

y=xw=uv(uv)ku=(uv)k+1u:

Denition

I.1.21.Soitw=w1w`unmot,avecwi2pourtouti.

L'entierk1estuneperiodedewsi

w i=wi+k;8i=1;:::;`k:

I.1.Premieresdenitions7

exemple,lemot abbabbabba periodiquepourtoutp`. Lemme lui-m^emep-periodique.

Demonstration.C'estevident.

Theoreme

Lemme denie6par f(x)=x+psi0xMath.Soc.16(1965),109{114.

8ChapitreI.Motsetlangages

Wilf. pouqcommeperiode. q=d1 w iwi+dwi+(k1)d;i=1;:::;d Exem optimale: abaab {z}abaab |{z}abaab |{z}a 1. w que w R=w; alorswestunpalindrome.

Denition

I.1.26.Unmotnidelaformeauauaouu2eta2est

unchevauchement(enanglais,overlap). a u a u a Pro

I.1.Premieresdenitions9

t=abbabaabbaababbabaababbaabbabaab Lemme bxbn'appartiennentpasaX. unecontradiction. Lemme waussi.Supposonsquef(w)sefactoriseen f(w)=xcvcvcy;c2fa;bg;x;v;y2fa;bg:

Montronsapresentquejvjestimpair.

paritedejxj. f(w)=x|{z} paircimpairz}|{v| {z} paircv|{z} paircy2fab;bag x,f(s)=cv,f(t)=cyet w=rsst:

10ChapitreI.Motsetlangages

f(w)=xc|{z} pairimpair z}|{vc|quotesdbs_dbs24.pdfusesText_30

[PDF] CH.3 SYSTÈMES D`EXPLOITATION

[PDF] Ch.4 - La place de l`Union européenne dans le contexte monétaire - Énergie Renouvelable

[PDF] Ch.6. Exercice corrigé p : 174 n°17. APPLICATION DES LOIS DE - Amélioration De L'Habitat Et De Réparation

[PDF] CH.7 LA GRAVITATION UNIVERSELLE – activité 1

[PDF] CH.7 LA GRAVITATION UNIVERSELLE – activité 2 - France

[PDF] Ch.8 DISPERSION ET REFRACTION DE LA LUMIERE I. NATURE - Anciens Et Réunions

[PDF] CH.8 LE CIRCUIT ÉLECTRIQUE – exercices

[PDF] CH.9 LE CIRCUIT ÉLECTRIQUE – exercices - Anciens Et Réunions

[PDF] Ch.9. Cours. TEMPS ET ÉVOLUTION CHIMIQUE : CINÉTIQUE ET

[PDF] CH02 - Probleme Juridique

[PDF] Ch02-Triangle et cercle circonscrit - Prêts Étudiants

[PDF] ch0402 - archives (SCMO)

[PDF] Ch05_i11568 Hemo FR - Société Canadienne de l`Hémophilie

[PDF] ch0704 - archives (SCMO) - Canada

[PDF] Ch1 - Activité documentaire 1