Théorie des automates et langages formels PDF

Toute syncope doit faire rechercher par l'interrogatoire par l'examen clinique et par d' plupart survenant au cours des 2 premières années (classe 1).

Théorie des automates et langages formels

Chapitre I. Mots et langages. 1. 1. Premi`eres définitions. 1. 2. Langages. 10. 3. Expressions réguli`eres et langages associés. 15. 4. Exercices.

Comment les comptables peuvent contribuer à la résorption du

L'ACCA (Association of Chartered Certified Accountants) est un organisme mondial pour les comptables professionnels qui offre aux apprenants du monde entier

Combler lécart par rapport aux attentes en audit – La voie à suivre

est le fruit de l'examen mené par l'Association of. Chartered Certified Accountants (ACCA) en collaboration exercice machinal;.

ifrs-9-instruments-financiers.pdf

Au cours des périodes ultérieures l'entité doit comptabiliser tout produit tiré faible de la juste valeur de l'actif transféré et du prix d'exercice de ...

Manuel de la réglementation du transport aérien international

un État à l'intérieur de son territoire dans l'exercice de sa naire de l'aviation civile de l'État hôte)

Formations et certifications Aruba 2020

1 nov. 2019 La même politique s'applique à Aruba Edge Associate et Aruba Edge Expert. Si un candidat détient trois à quatre certifications l'examen écrit ...

Reconnaissance des qualifications

d'un titre sanctionnant une formation réglementée directement orientée vers l'exercice de la profession comptable) ;. - avoir subi avec succès un examen

NORMES COMPTABLES INTERNATIONALES POUR LE SECTEUR

d'examen qui concernent la vérification et la révision d'états financiers potentiel de service au cours de l'exercice sous forme de sorties ou de.

INFORMATION & COMMUNICATION

Au travers d'exercices et de stages la formation pratique dans ces domaines L'étudiant ne peut passer plus de deux fois le même examen au cours d'une.

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

1wk2,ondenotepar

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

2etjabbacjc=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| {z} pairvc|{z} pairy2fab;bag conclusionestidentique. ment. Remar

Soitlemorphismeg:fa;b;cg!fa;bgdenipar

g:8 :a7!abb b7!ab c7!a: Pro carre. parlam^emelettre.

2.Langages

8Onremarqueraquefa;ab;abbgestuncode.

I.2.Langages11

Ondistingueenparticulierlelangagevide9;.

Exem fa;aa;bbc;ccca;abababg pairdeaestaussiunlangage(inni), L entierspositifspairsestunlangagesur f10;100;110;1000;1010;1100;1110;:::g f10;11;101;111;1011;1101;10001;:::g: tion.

Denition

langagesLetMestlelangage

LM=fuvju2L;v2Mg:

par L n=fw1wnj8i2f1;:::;ng;wi2Lg L baba;baac;aca;acab;acba;acacg: contenantuniquementlemotvide. i=0wi2i.Engeneral,

12ChapitreI.Motsetlangages

concatenationdemotsdeX. Pro L

1(L2L3)=(L1L2)L3;

1f"g=f"gL1=L1;

1;=;L1=;;

1(L2[L3)=(L1L2)[(L1L3);

(L1[L2)L3=(L1L3)[(L2L3):

Demonstration.C'estimmediat.

Denition

L i0L i: nombrearbitrairedemotsdeL. Remar

Onrencontreparfoisl'operationL+deniepar

L i1L i: L nf"g. Pro petit12langageMtelque"2M,LMetM2M. (1956)Ed.C.Shannon,J.McCarthy.

12Lepluspetitpourl'inclusion.

I.2.Langages13

s'apercoitque L iM;8i>0:

Ceciconclutlapreuve.

Theoreme

existeunlangagefini

FtelqueL=F.

pluscourtappartenantaLnfapg.Deslors, q

1=t1p+r1;avec0 q
2=t2p+r2;avec0
Eneet,q2>q1etsir2=r1,alorsonaurait
q
2=(t2t1)p+t1p+r1|
{z} =q1: raisonnementindenimentetnalement L =fap;aq1;:::;aqsgavecsp1:
Denition

Pref(L)=[
w2LPref(w) onpose
Su(L)=[
w2LSu(w)etFac(L)=[ w2LFac(w):
14ChapitreI.Motsetlangages

Denition
fest f(L)=ff(u)2ju2Lg: parlemorphismefest f
1(M)=fu2jf(u)2Mg:
Exem par f(a)=;f(b)=;f(c)=:
SiL=fab;bc;cb;aaab;aaacg,alors
f(L)=f;;g:
SiM=f;;g,alors
f
1(M)=fab;ac;ba;ca;bab;bac;cab;cacg:
Remar \morphismenoneacant").
Denition

I.2.14.Lemiroird'unlangageLest
L
R=fuRju2Lg:
despalindromes.
Denition
par
Com(L)=fw2j9u2L:82;jwj=jujg:
que
Com(L)= 1 (L):

Denition
uttv=fu1v1unvnju=u1un;v=v1vn;ui;vi2;n1g:
Parexemple14,siu=abetv=cde,alors
uttv=fabcde;acbde;acdbe;acdeb;cabde; cadbe;cadeb;cdabe;cdaeb;cdeabg:
Leshuededeuxlangagessedenitcommesuit,

LttM=[
u2L; v2Muttv: toirecontenantdiverschiers: >lsmonrepertoire/ memoire.oldpicture002.jpgprice-list.txt memoire.logpicture003.jpgtaches.txt comme ls.jpg executera rmm precedentessections. serverladenominationanglo-saxonne. dantlesm^emeslettres.
16ChapitreI.Motsetlangages
surestdenirecursivementpar
I0eteappartiennentaR,

Ipourtout2,appartientaR,

Isiet appartiennentaR,alors
{(+ )appartientaR, {(: )appartientaR, {appartientaR. Exem lieres:
1=(e+(a:b));

2=(((a:b):a)+b);

3=((a+b):(a:b)):
L:R!2 par
IL(0)=;,L(e)=f"g,

Isi2,alorsL()=fg,

Isiet sontdesexpressionsregulieres,
{L[(+ )]=L()[L( ), {L[(: )]=L()L( ), {L()=(L()). Exem pleI.3.3.Poursuivonsl'exempleI.3.2.Ona
L(1)=f";abg;

L(2)=(fabag[fbg);

L(3)=fa;bgfabg:

Denition
reguliere2Rtelleque
L=L():
Siet sontdeuxexpressionsregulierestellesqueL()=L( ),alorson ditqueet sontequivalentes. Remar super us.Parexemple, (((b:a):(b:a)):b)=(baba)b l'expression b (abab): Pro concatenationetd'etoiledeKleene. devonsverierqueL(R)A.SoitLunlangageregulier.Ilexiste 2 R telqueL( )=L.Onprocedeparrecurrencesurlalongueur16de l'expressionreguliere :
Si vaut0,eou(2),alorsL( )vaut;,f"g=;oufg.Par
consequent,LappartientaA. Si =(+)avecetdesexpressionsregulieressurdelongueur inferieureacellede ,alorsona
L( )=L()[L():

Si =(:)ou =,onutiliselem^emeraisonnement.
Remar vudesproprietesdestabiliteenoncees. Pro positionI.3.8.Soit uneexpressionreguliere.Ona
I + = ,

Ie = e= ,

I0 = 0=0,

I( )= ,

I = 0+ 1++ k+ k+1 ,

I( +)=( ) .
;deuxexpressionsregulieres.Si =0;eou(2),alorsj j=1.Deplus, j( +)j=j j+jj+1,j( :)j=j j+jj+1etjj=jj+1.
18ChapitreI.Motsetlangages
exactementleslangagesdelaforme fiji2Ag p+N:q=fp+n:qjn2Ng avecp;q2N.
Ici,l'application
jj:fg!N:n7!n
I;2P(casdel'unionvide),

If1g2Pcarf1g=1+N:0,
q=0,alors (p+N:q)+(r+N:s)=(r+p)+N:s2P:
Siq>0,alors
(p+N:q)+(r+N:s)=[
0i n=`q+i;0iParconsequent,
t=p+r+mq+(`q+i)s=p+r+is+(m+`s)q avec0iOnpeutdenirl'etoiled'unepartieAdeNpar
A =fa1++anjn2Net8i2f1;:::;ng;ai2Ag: commutative, (A[B)=A+B
Sip=0,(N:q)=fqg=N:q2P.Sip>0,
(p+N:q)=f0g[[
0i p+n1q++p+njq=p+(j1)p+(n1++nj)q: n
1++nj=mp+i;avec0i etdoncquotesdbs_dbs42.pdfusesText_42

[PDF] Théorie des automates et langages formels

Facultedessciences

Departementdemathematiques

Theoriedesautomates

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

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

Adenine,Cytosine,GuanineetThymine.

Denition

Denition

1wk2,ondenotepar

2etjabbacjc=1.

2ChapitreI.Motsetlangages

Denition

I.1.5.Soitw=w1w`unmotsur.Lesmots

Defaconsemblable,

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:

I.1.Premieresdenitions3

Denition

Onposew0=".

8u;v2:juvj=juj+jvj

4ChapitreI.Motsetlangages

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

I.1.Premieresdenitions5

1(a)=abc

2(a)=abcacb

3(a)=abcacbabcbac

FigureI.1.uv=vu.

6ChapitreI.Motsetlangages

FigureI.2.xy=yz,jxjjyj.