La thèse de Church

Description

Niveau: Supérieur, Doctorat, Bac+8
La thèse de Church Martinet Lucie 6 juin 2008

• automate


• modèle de calcul


• calculable e?ectivement?? calculable par machine de turing


• machine séquentielle


• ?? ??


• appelés lettres

Sujets

• Automate

Informations

• Publié par: mijec
• Publié le: 01 juin 2008
• Nombre de lectures: 33

Extrait

LucieLaMarth?sejuindetinetCh6urc2008hw∗w
Reconnaissancemati?res.1.Innestro.ductiontransfert2.2.Quelquesusd?nitions6.1sur.les.langagesacc?set.auto35matestiers3Une2.1.Les.langages..........41.de.....bre.a.35.....mots.......Les...............40...tr?le...T3hine2.2.Les.automates.ni.sBibliographie.?.rubans.de.T...deux.....la...t.fournit.......de.......acc?.........onctionnemen..4.2.2.1.LesInstructionsautomates.d?terministes.:40quelques.d?nitions.et.no-arithm?tiquestations....6.6.......d'une.une.Sim.par.6.8.1.......ADD.......7.mac.T.no.d...Pr?sen.tes.hines......4L'addition2.2.2bresIn.terpr?.ta.ti35omotsnablegraphique..37.hine.tous.l.t.ts...........5.6.et...........385hines2.2.3directLes.automates.nis.non.d?terministes........6.2..............7402.2.4tr?e/sortie?quiv.alence.en.tre.les.automatesInstructionsd?terministes.et.non.d?-.terministes....Op.............de.............Sim.hine.ng.hine.42.d'une.acc?s.mac.uring.2..8.2.2.5.Les.transitions.instan.tan?es44et.commen.t.les.?liminer.......114431Leshimacdehinesurings?quenuntiellmequelconquese12.4.Caract?risation5.5destationlangagesdi?renreconnmuscpardeunuringautomate.14.4.1.Les.langages.rationnel5.5.1sde.nom.en...............5.5.2.des.de.formedesT..........5.5.3.mac.d?cidan.si.les.qu'on.ui14son4.2toLesdi?renautomates.m.inimaux..................37.R?duction.l'alphab......................1.964.2.1macD?nition?.s.39.D?nition...............................39.F.t............19.4.2.2.Le.lemm.e.de.l'?toile....6.3.d'en.......................6.4.de..........22.5.Les.mac.hines.de.T.uring6.523?rations5.1.Les.mac.hi.nes.?.un.ruban........41.Instructions.con.........................6.7.ulation.mac.de.uri23par5.2macReconnaissance?d'undirectlangage6.8parulationunemacmac?hinedirectdeuneThineuringT.43.STORE......25.5.3.Les.mac.hi.nes.?.deux.rubans......6.8.2.3.............................44.Conclusion.828455.4Les⇐⇒
ttrotductiond'?tapLas'agitth?sededeutilis?es,ChparurcnoushtepropToseEncommonsedemol'?toiled?lecesdeLescalculossibilit?lesexemplesmacdehinescalcul,deeTmoturing.unIci,unous4.negagesclesherclesheronsacc?spasreconna?tre?ded?monentrerm?mecetteplusieursth?se,alenceTquiqueesteecimphineossi?treble,clair.nise?ermettenlalecture,r?futer.ourNoustal.pr?senuneteronsquiplut?td'unlespartie,outilssonmath?matiquestquiourp?nonceronsermdansettenTtd?ledemonl'?noncerpeteectuerdefairelat?ecomprendre.TLessenm?thooudesvmath?matiquesulsexperronsos?essonicicettesonma-tse?celles-ci.laChbaseandeparcth?se,ellesputilis?escepunourcel'implanl'?quivtationh,des2langagescelles-cidel'impressionprogrammationscourssursonmacparticulier,hine.imLaulth?speexempledehineChnurclehlaproptieroseunedevd?nirpr?cise,lalesnotionouvdereconncalculautomate.enousrationnelseth?or?mectifNouscommequatri?mecalculhineseectuable:parautremaccalculhinetiel.dereronsTcuring.enUnlangagescalculcalculs,eectifour-estuneunrecalculunquihinesd?-pmonsetresousqu'uneformessolution,rubans,?nousunlaprobl?menosdonn?,uneexiste.NousDecesplus,maccetoutescalculNousdonneparuneconstructionm?thohinesdeppvour?trorappuvth?seerhcemani?rette:solution,emenInc'esthine?D'apr?sdireunequ'ilTpr?senfaireteestunepproec?-bredured?termiouuiunourcalcul,propquiChsefauttermvinepartie.eneet,unpnomtbred'unniend'?tapdeesetd?terministes,touencepqu'onsappulerellecalcplusmencourammenNoustouvunparalgorithmeconstruire.macLes?qprobl?meeesttielledonccalculedequotiend?nirdeladivisionnotionend'eectivparit?,Dansquitroisi?mesenousr?f?reerrons?fa?onunquelsmotd?lelan-depcanalcul?tre.usC'estunpPourquoi,cela,nousd?crironspr?senlangagesteronsetdi?renletsdemo.d?le?tudierons,sunedepartie,calmaccul,de?uringcilod'unmmomencerdepar?less?quenautomates,Nousdonttquenousma-monhinestreeuvrontsdeslesetlimites.desDansqueunperionspremi?resurpartie,feuillenouspapier,commenceronspr?senparpardoruban.nnemacrdequelquesuringd?ni-euvtionstsurpr?lesterlangagesdi?renetesles(unautomatesplusieursd?terdeministes.queNaoonsusppr?send'organiserteronscalcesurnsuite,oulesfeuilles).automatesvnonqued?terministesdi?renets?tablironshinesleurt?quiv?quivalencetes.atermineronsvpartieecquelqueslesdeautomatesded?terministes.cApr?sdecela,uringnousour?vconoaincrequeronsl'eectivitquelquesdevNousarianelonsteslad'automates,dequiurcps'?nonceermettenlatsuivdetefacilitercalculablelestivconstructions.t1Commecalculablelesmacautomatesdeneuringdonnencettetsipasmacldeauringpeutossibilit?und'?crire,c'?quel'incalculveutersed?critdesnmacnomhinesnis?quenestiellesnistes,,qnouspara?t?Ptudieronsobtenirbri?valenceemos?enparturccesilderni?resdoncdansconuneaincrese-condew
L
Σ Σ
∗Σ
Σ Σ
∗w Σ
w w
w w
ε
v w Σ
v w
v w
v w v.w vw
ε
n nw n w n = 0 w = ε
∗Σ Σ
∗
L {0,1}1
L {a,b}2
a b
n na b L {a b }2
deecmotslesenmacquihinesz?ro.debTtouteuring.conca-2noteQuelquesded?nitionsdessurtlesD?nitionlangageslangethineauto-etmatesos?.Lesmotautomatesprogrammationpdeermettenlettrestsede?rationdonnerOnunemacvunersionVformalis?etsdubrecalculmacmen-esttal,tvc'estt?mdireOnsansl?critureSoienpunossible.elleNouslep?ouvsuiviesonsdegr?ceeaucoup?concat?nationeux,dond?criremotdelamani?re.simplepartie,,appdesblangagesderelativdeeform?menourtrepr?sencompliqu?s.2.Lestsautomates,quicommeform?lessuitemacconhinesdede?Tdouring,estr?longueurpaujourd'hondenutilisonstnous?donllongueura2.3questionque:motslealphabmotOnc'estoncappartienett-ilobtenauanlangagesuite,erse,langag?lettresCesLadeuxetmoprod?lessimplemende.calculunesonciativtl'?ltr?sestutisonlis?sderni?resendeinformatiquetiquescar?ilalorssderni?rson.tlangageutilesldansuneplusieursrapplications,terons,notammquelquesen1.tpr?senp?l?meournol'analyseuring.lexitcale.d'unDeparplus,langageleurdesimpl?menl'alphabtationcalculableetstd'unassezsuitefaciled'eteilsudonctprqualiablea.tiquequebre?lettresutiliser.nAui.vcompanLatdud'abotordersela|d?nition|.concr?tenotedesleautomates,vide,itlanousestfautD?nitiond?nir.lestdi?renettsdeuxobsurjetsm?medonett.unappautomatecestat?nationcompsos?e.mot2.1uLes?crivlangagest,D?nitionla2.1les.deOn,appdeselledealphab.etconcat?nationtouthesensemcblenoteniplusnonouvtidetdeLasymestbopoles.assoLese,?l?mentts?mend'unneutrealphableetvidev.sonnotetCesappconcat?nationel?sdirect.lettridenesacc?s.SiUnhinesalphab,elestein.est2.4uneOnsuiteelleniesurdealettres.phaOnetnote,implicationpal'tiel'ensemdansble.desoicimotsexemplesplangagesouvLeanagetus?tredesform?sn?departircela,desPlettresTdesondelaatationbinaire3nomalencedivisible?quiv4.tLeendefaitform?une?l?mensuitedenieetdeparlettresbiendesonleurla.t?nationD?nitionmot2.2d'une.deSoitpuistreronsuneundmotd'eectifdeqmoninoustien.autanOndeappqueellecalcullongueurtoutde=Enn,direlenommotsson..LesP
ε P
v w P vw
P
∗ ∗Σ = {(,)} γ Σ −→ Σ
∗w∈ Σ (w)
w P γ(w) = (w) P
0L L
0L∪L
0LL
0 2vw v∈L w∈L L LL
∗ nL L n
0L {ε}
Σ
δ
δ : Q×Σ−→ Q
(p,a)7−→ q
a
p−→ q;
p0
F F
¯δ δ
∗¯δ : Q×Σ −→ Q
w
?deuxtlangagestsuretunlealphabbienet,d?nitionsalorsd'uneonappartiend?nit?tats:?i)mthaquesonestetideSiiii)la?crirarnot??uniontsdes.deuxquilangagesmais;arii)ositif.essage?automatesle2.5prd'unoensembleduitnot?deansitionctoncmotsat?nationii),dqui5.estdesl'ensmtble?tatsdestmotsdepdeouvplusan:tlangages'?lecrired'unsipusun,dea2.2.1v:ecnotationsaUnt:appartienetet2.alorsnon,?tats?;tde.:On??critalorsappartienappartiennenSiquele:langage?.d'un.d?piii)motciesous-ensemassol'ensemlaLesr?unioni)desel?slangagesoudeclamainformefonctionmotpartitout,,ppd'unourautre,?uneenuntier.d?niNousparencon3.viendronscurrenceque?trequiuni:dispestluileermettanlangaged'?mettrevidemfonctionlorslacsoittransition..LesCesd?terministesquelquesquelquesd?nitionsetdonn?es,D?nitionnous.pautomateouvconstitu?ons1.mainalphabtenannit;d?crid'unrenicevqu'estd'un,automate.Q2.23.Lesfonctionautomatestrnisl'alphabUnsoitautomate.niencoreesappartien,,,toetiendeux:l'onouvaussiansit.settrouv4.er?tatdanseunartnomvidebre;nid'undeblecongurationsdedi?renbletes,?tats.aussi?l?menappdeel?esson?tatsapp.lesL'automatenauxre?oitencoreuneacsuiteeptantsd'instructionsD?nissons(soustenanformlae:de?signaux),rquisuiprocevnousoermettraquepasserun?tatcunhangemennontpard'?tat,lettre,aussiparappmotel?commetrform?es,ansitionth?ses.desUnLeautomatePpr?eutsur?galemenmotttonunebtmacthine4p¯δ(q,ε) = q

¯ ¯δ(q,wa) = δ δ(q,w),a ∈ Σ
LM M
∗Σ
n o
w
L(M) = w : p −→ F0
M w
a
?>=<89:;/.-,()*+ 89:;?>=<
b
n
(ab) n≥ 0
outir:cercl?s.parled?niou-detionbleestsous-ensemdiagramme.lequiOnnnieditlesaussi2.que?tatsl'automateestcommet?ac2.6.ctepteestautomate?.ebuts2.2.2parInreconnaissanterpr?tation3.graphique?cUntautomatemotpceutpar?tretrepr?senunt?rde?tatdi?rennetesnmani?res.enIleutpLaeuttous?tren'apparaissenrepr?senemplest?(sousFig.formeedetransitiontableaude?pardoubleetenuxtrmen?ec(?tatsparpci?ourinlmotseslangagelignesl'automate,etquilettrestpnal.ourapplesuncolonnes),pasconmaistenandestermetlesunv.aleursblodeouclelanefonctionbde?tattravn-eutsition.esCetteunrepr?senpastationQuelquesn'est/pasreconntr?s’vgisuellemaislepaermet;l'impl?menconsid?r?e.tationL'?tatded?partl'automatemarqu?dansuneunhelangagelesdenaprogsonramdouble-mationtquelconque.APhaqueourtrait?faciliterl'automate,laassolecture,unnoushemcduhoisironsLesplut?taccept?sdelerepr?senrepr?senteparrsonnosceuxautomates,abpartissenun?diagramm?tateD?nitionquiOnseelleliebutt?tatden'estlaunmani?renal,suivdonanaucunetetransitions:p1.d'abLes??tats?tatsonalt(L'automaterepr?senainsit?squ?parbdesiunet5pconatenanoutirtun?vnal.)encontuellemenentvlequenomlderl'?tatd'enautomatequestion.t2.surLesdiagrammes.transitionsexsond'automat