[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: De ce nu începem. Așadar, așa cum îmi place să fac, să trecem în revistă unde am fost recent, adică să discutăm despre limbile fără context. Am vorbit despre gramaticile fără context și despre automatele pushdown ca o modalitate de a descrie limbajele fără context. După cum vă amintiți, limbile fără context sunt o clasă mai mare de limbaje decât limbajele obișnuite, de unde am început, limbajele automatelor finite. Deci, atunci când adăugați o stivă, obțineți mai multă putere. Obțineți mai multe limbi pe care le puteți face. Și astăzi vom trece foarte repede la modelul nostru principal pentru semestru, care se numește mașina Turing. Deci, să aruncăm o privire la ceea ce vom acoperi astăzi. Și aceasta este, mai întâi, vom arăta că o tehnică analogă cu cea pe care o folosim pentru a demonstra că limbile nu sunt obișnuite, dar de data aceasta pentru a demonstra că limbile nu sunt lipsite de context. Deci, automatele pushdown și gramatica au încă limitările lor în ceea ce privește ceea ce credem în mod normal că poate face un computer. Și cu asta, vom folosi asta ca un fel de introducere la modelul nostru de uz general, care este mașina Turing. Și așa vom vorbi despre mașinile Turing și despre aspectele acestora. Aș dori să comentez, așa că am postat soluțiile pentru primul set de probleme. Știu că acum începi să te gândești la al doilea set de probleme , pe care l-am postat și eu. Dacă vrei să-ți faci o idee despre ceea ce caut în ceea ce privește nivelul de detaliu, poți să te uiți la soluțiile pentru setul de probleme unul, pentru că le consider soluții model. Acesta este o parte din motivul pentru care le postez, doar pentru a vă oferi o idee despre nivelul de detaliu pe care îl caut, care nu este foarte mult. Dar vreau să mă asigur că captați ideile principale despre ceea ce este implicat în rezolvarea problemei. Deci aruncați o privire la acestea. Și pentru setul de probleme doi, despre care voi vorbi într-o secundă, așa că voi spune doar câteva cuvinte. Dacă vrei să tragi asta , poți face asta. Dar doar pentru a începe cu câteva dintre probleme, dacă găsiți unele provocări acolo... Nu vreau să rămâneți blocat chiar înainte de a înțelege ce spune problema. Deci, pentru problema numărul unu, dacă te-ai uitat la asta, deci este o problemă în care ți se cere să dovedești că o anumită limbă nu este lipsită de context. Și, apropo, toate problemele din această problemă s-au stabilit, cu excepția poate ultimei, pentru numărul șase, pe care le vei putea rezolva. Vom avea suficient material la sfârșitul prelegerii de astăzi pentru a le rezolva pe toate. Eu cred că este corect. Da, deci numărul șase, ar trebui să ai suficient de la prelegerea de joi pentru a rezolva asta. Deci problema numărul unu, demonstrează că o limbă nu este lipsită de context. Așa că vom introduce o metodă pentru a face asta. Această metodă va fi utilă. Pentru părțile B și C, dacă te uiți la setul de probleme, are acest lucru ciudat, sigma sigma sigma în stea dintre paranteze. Este într-adevăr doar o expresie obișnuită, care este foarte simplă. Ar trebui să vă asigurați că înțelegeți că acesta este un mod de a reprezenta toate șirurile a căror lungime este un multiplu de 3. Și dacă lipesc un sigma în fața acestuia, sunt toate șirurile a căror lungime este 1 plus un multiplu de 3. Deci, odată ce ați înțelegeți asta și, dacă vă gândiți la ce tipuri de șiruri sunt în limbajul C2, vă va ajuta să înțelegeți ce se întâmplă când luați acele uniuni. Iar părțile B și C nu se intenționează să fie foarte grele, dar trebuie doar să înțelegi ce se întâmplă. Problema numărul doi este despre gramatici ambigue. Am atins asta pe scurt în prelegere. Este suficient pentru a rezolva problema. Cartea conține puțin mai multe detalii despre limbile ambigue, gramatici ambigue - gramatici ambigue, ar trebui să spun. Și deci aceasta este o gramatică care ar trebui să reprezinte un fragment dintr-un limbaj de programare cu if thens și if then elses. Sunt sigur că sunteți cu toții familiarizați cu aceste tipuri de construcții în limbaje de programare. Și există o ambiguitate naturală care apare într-un limbaj de programare. Dacă aveți dacă o condiție, atunci declarația unu, altfel afirmația a doua, presupun că înțelegeți care este semantica acesteia, ce înseamnă aceasta. Și lucrul complicat este că dacă ai... acele afirmații pot fi ele însele declarații if. Și deci, dacă aveți situația în care aveți dacă atunci și dacă atunci altceva este ceea ce urmează, întrebarea este, de unde se atașează celălalt? Este pentru al doilea dacă sau pentru primul dacă? Deci, acesta este un fel de mare indiciu asupra acestei probleme, dar este în regulă. Trebuie să luați asta și să vă dați seama cum să obțineți un membru real al limbajului care este generat în mod ambiguu, apoi să arătați că are - să arătați că este prin arătarea a doi arbori de analiză sau două derivate din stânga. Dacă citiți cartea, veți vedea că este o modalitate alternativă de a reprezenta un arbore de analiză. Deci, ceea ce ar trebui să faci este să dai o gramatică pentru aceeași limbă, care nu este ambiguă. Nu trebuie să demonstrezi că nu e ambiguu, pentru că asta e o corvoadă. Dar atâta timp cât înțelegi ce se întâmplă, ar trebui să poți veni cu o gramatică fără ambiguități care să rezolve această ambiguitate. Și nu am în minte să schimb limbajul prin introducerea de noi constructe de limbaj de programare, cum ar fi un „început sfârșit”. Asta nu este în spiritul acestei probleme, pentru că este o altă limbă, este o gramatică diferită. Deci, trebuie să generați aceeași limbă fără alte lucruri străine care să rezolve ambiguitatea. Ambiguitatea trebuie rezolvată în cadrul structurii gramaticii în sine. Așa că ține cont de asta. Pentru problema numărul trei despre automatele de coadă, știi, asta a apărut de fapt ca o sugestie ultima prelegere, cred, sau două prelegeri în urmă. Ce se întâmplă dacă iei un automat pushdown, dar în loc de pushdown-- în loc de stivă, adaugi o coadă. Ce se întâmplă atunci? Ei bine, de fapt, se dovedește că modelul pe care îl obțineți este foarte puternic. Și se dovedește a fi echivalent ca putere cu o mașină Turing. Deci veți vedea argumente de acest gen astăzi, cum arătați că alte modele sunt echivalente - nu, nu astăzi. Așa că îmi cer scuze. Acesta va fi ceva ce vei... Mă confund aici. Problema numărul trei are nevoie de fapt și de prelegerea de joi pentru a vedea cel puțin exemple despre cum faci așa ceva. Da, așa că voi încerca să trimit o notă care să clarifice asta. Până la sfârșitul zilei de joi, vei putea face totul, cu excepția problemei șase. Și pentru problema șase, vei avea nevoie de prelegerea de marți, la o săptămână de la prelegerea de azi. Deci problema numărul patru, aceea pe care o vei putea face la sfârșitul zilei de astăzi. Și asta va... problema este că și eu lucrez la pregătirea prelegerii de joi. Așa că devin puțin... mă încurc. Problema numărul patru, o vei putea rezolva după prelegerea de joi. Poate ar trebui să vorbim despre următoarea prelegere. Problema numărul cinci, o poți face azi, dar poate nu voi spune nimic despre asta. Și problema numărul șase, nu voi spune nimic nici despre. OK, atunci de ce nu ne aruncăm și ne uităm la materialul de astăzi. Ce spui de șapte? Oh, șapte este o problemă opțională. Oh, ar fi trebuit să menționez asta. Șapte va fi întotdeauna o opțiune. Indică faptul că cu o stea ar fi trebuit să explic acest lucru în descrierea actuală de aici, dar șapte este opțional. Este exact ca și cum am avut pentru setul de probleme unul. OK, să trecem, să trecem, atunci, la ceea ce vom vorbi astăzi. Și doar o mică revizuire, așa că am vorbit despre echivalența gramaticilor fără context și a automatelor pushdown, așa cum vă amintiți. Hopa, lasă-mă să ies din imagine aici. După cum am menționat data trecută, am demonstrat de fapt o direcție, dar cealaltă direcție, trebuie doar să știi că este adevărat, dar nu trebuie să cunoști dovada. Dovada este un pic lungă, aș spune. Este o dovadă frumoasă, dar este destul de lungă. Și există două corolare importante în acest sens. Dacă știi ce este un corolar, este doar o consecință simplă care nu are nevoie de prea multe dovezi, un fel de consecință foarte simplă. În primul rând, cred că am subliniat data trecută, o concluzie, un corolar pe care îl obțineți este că fiecare limbaj obișnuit este un limbaj fără context, deoarece un automat finit este un automat pushdown care pur și simplu nu își folosește stiva. Deci imediat, înțelegi că fiecare limbă nu are context. Și, în al doilea rând, înțelegi imediat că, ori de câte ori ai o limbă fără context și o limbă obișnuită și iei intersecția lor, primești înapoi o limbă fără context. Deci, intersectul regulat fără context este fără context. Asta este de fapt menționat în temele tale, precum și una dintre problemele 0.x pe care le dau pentru a încerca să te obțin -- nu trebuie să le predai, dar îți sugerez să te uiți la ele. Nu știu câți dintre voi vă uitați la ele. Dar acesta este un fapt util. Și unele dintre acele alte fapte din problemele 0.x sunt utile. Așa că vă încurajez să vă uitați la ele. Dar oricum, intersecția dintre context liber și regulat este fără context. S- ar putea să vă întrebați, cum rămâne cu intersecția dintre fără context și fără context? Avem închidere sub intersecție? Răspunsul este, nu, nu avem aproape de închidere sub intersecție. Vom vorbi despre asta în curând. Deci, aici este schița dovezii pentru... Am vrut să spun că intersecția dintre context liber și regulat, de ce știm că este încă fără context? Deoarece automatul pushdown pentru A poate simula automatul finit pentru B în interiorul controlului său finit, în interiorul memoriei sale finite. Problema este că, dacă aveți două limbi fără context, aveți două automate pushdown, nu puteți simula asta cu un automat pushdown, deoarece are doar o singură stivă. Deci, dacă încercați să luați intersecția a două limbi fără context cu o singură stivă, veți avea probleme, pentru că este greu să... oricum, asta nu este o dovadă, dar cel puțin îți arată ce merge prost dacă încerci să faci lucrul evident. Bine, deci dacă... și doar, iată un punct important pe care încercam să îl subliniez înainte. Dacă A și B sunt ambele fără context și luați intersecția, rezultatul poate să nu fie neapărat un limbaj fără context. Deci clasa de limbi fără context nu este închisă sub intersecția sa. Vom comenta asta în scurt timp. Limbile fără context sunt închise în cadrul operațiunilor obișnuite, totuși, unire, intersecție-- unire, concatenare și stea. Așa că ar trebui să te simți confortabil că știi cum să dovedești asta. Din nou, este una dintre... Cred că este problema 0.2. Și cred că soluția este dată chiar în carte pentru asta. Așa că ar trebui să știi cum să demonstrezi asta. Este destul de simplu. Bine, deci haideți să trecem la încheierea lucrării noastre despre limbile fără context, să înțelegem limitările gramaticilor fără context și ce tipuri de limbi ar putea să nu fie fără context. Și cum demonstrezi asta? Deci, cum demonstrezi că, pentru o anumită limbă, nu există gramatică? Din nou, știi, nu este suficient doar să, să zicem, să dau un comentariu informal că, nu m-am putut gândi la o gramatică sau la niște... lucruri de acest gen. Asta nu va fi suficient de bun. Trebuie să avem o dovadă. Deci, dacă luăm limbajul aici, 0 la k, 1 la k, 2 la k, deci acelea sunt șiruri care sunt rânduri de 0 urmate de un număr egal de 1 urmat de un număr egal de 2, deci doar 0 , apoi 1, apoi 2, toate de aceeași lungime. Aceasta este o limbă care nu va fi o limbă fără context. Și vom oferi o metodă pentru a demonstra asta. Dacă ai avut o stivă, poți potrivi 1-urile cu 0-urile, dar odată ce ai terminat cu asta, stiva este goală. Și cum te asiguri acum că numărul de 2 corespunde cu numărul de 1 pe care l-ai avut? Deci, din nou, acesta este un argument informal care nu este suficient de bun pentru a fi o dovadă, dar dă un fel de intuiție. Așa că vom oferi o metodă pentru a demonstra că nu sunt lipsite de context -- limbile nu sunt lipsite de context folosind, din nou, o lemă de pompare. Dar aceasta va fi o lemă de pompare care se aplică limbajului fără context, nu limbajelor obișnuite. Arată foarte asemănător, dar are câteva riduri în plus, deoarece cealaltă lemă de pompare mai veche era specifică limbilor obișnuite. Și acesta va fi ceva care se va aplica limbilor fără context. OK, deci acum hai să-l citim. Și apoi vom încerca să o interpretăm din nou. Este foarte asemănător ca spirit. Practic, spune că, ori de câte ori ai un limbaj fără context, toate șirurile lungi din limbă pot fi pompate într-un fel. Așa că va fi un fel de pompare puțin diferit decât am avut înainte. Și rămâi în limbă. Bine, așa că înainte, am rupt sfoara în trei bucăți unde am putea repeta piesa centrală de câte ori doriți. Și rămâi în limbă. Aici, vom sfârși prin a rupe sfoara în cinci bucăți. Deci s va fi împărțit în uvxyz. Și cum va funcționa aici... deci iată o imagine. Deci, toate șirurile lungi... din nou, va fi un prag. Deci, ori de câte ori ai o limbă, va exista o anumită lungime. Deci, toate șirurile mai lungi în limba respectivă pot fi pompate. Și rămâi în limbă. Dar șirurile mai scurte, nu există nicio garanție. Deci, dacă aveți un șir lung în limbajul lungimii cel puțin această lungime de pompare p, atunci îl puteți împărți în cinci bucăți. Dar acum este a doua și a patra șiră care vor juca acel rol special de pompare, ceea ce înseamnă că, ceea ce poți face este să le poți repeta și să rămâi în limba. Și este important să le repetați pe amândouă, acel v și acel y, de același număr de ori. Deci vei avea o poză care arată cam așa. Și asta te va repeta. Dacă repeți v și repeți y, obții uvvxyyz. Sau dacă te uiți la aici, ar fi uv pătrat xy pătrat z. Și asta va fi încă în limbă. Și apoi avem... deci asta e o condiție. Va trebui să ne uităm la toate aceste condiții când vom face dovada, dar vrem doar să înțelegem care este afirmația chiar acum. Deci, a doua condiție este ca v și y împreună să nu fie goale. Și într-adevăr, acesta este un alt mod de a spune, nu pot fi amândoi șirul gol, pentru că dacă ar fi amândoi șirul gol, atunci repetarea lor nu ar schimba s. Și atunci, desigur, ar rămâne în limbă. Deci ar fi oarecum lipsit de sens dacă li s-ar permite să fie goale. Și ultimul lucru este, din nou, că va fi acolo ca o chestiune de comoditate pentru a demonstra că limbile nu sunt lipsite de context, pentru că trebuie să vă asigurați că nu există nicio modalitate posibilă de a tăia șirul. Când încercați să demonstrați că o limbă nu este lipsită de context, trebuie să arătați că pomparea eșuează. Va fi util uneori să limitați modurile în care poate fi tăiată sfoara, pentru că atunci aveți... este o treabă mai ușoară pentru dvs. să lucrați cu el. Așa că aici, este puțin diferit față de înainte, dar cam similar, acea combinație vxy ca subșir. Așa că arăt asta aici. vxy împreună nu este prea lung. Deci vxy-- poate că este mai bine văzut aici sus-- va fi, cel mult, p. Vom face un exemplu într- un minut de utilizare a acestuia. OK, deci din nou, iată lema noastră de pompare. Tocmai am reafirmat-o. Așa că o avem în fața noastră. Și vom face o dovadă. O să-ți dau mai întâi ideea dovezii. Și apoi vom trece prin câteva detalii. Ideea este de fapt destul de simplă. Îi dăm... Numiți-i o dovadă prin imagine. Din nou, amintiți-vă ce încercăm să facem. Încercăm să arătăm că avem acest limbaj A fără context. Și acum toate șirurile lungi din A au această calitate de pompare, că le puteți împărți în cinci bucăți, astfel încât a doua și a patra bucată să poată fi repetate. Și rămâi în limbă. Deci, de unde știm că asta va fi adevărat? Să aruncăm o privire la dovada aici. Și de ce va fi adevărat? Deci, în primul rând, aș dori să o fac mai degrabă calitativ decât cantitativ. Deci, să ne imaginăm, în loc să ne gândim -- vom calcula ce este p mai târziu. Dar imaginați-vă că este un șir foarte, foarte lung. Așa îmi place să mă gândesc la asta. Deci s este foarte lung. Ce ne va spune asta? Ne va spune ceva important despre modul în care gramatica produce s, ceea ce va fi util pentru a obține o modalitate de a le pompa. Deci, dacă s este cu adevărat lung, ne vom uita la arborele de analiză pentru s. Și vom concluziona că arborele de analiză trebuie să fie cu adevărat înalt, deoarece este imposibil ca un arbore de analiză foarte puțin adânc să genereze un șir foarte lung. Și din nou, vom cuantifica asta într-o secundă. Dar intuitiv, cred că nu este prea greu să înțeleg de ce ar trebui să fie adevărat. Deci, dacă aveți un s lung, arborele de analiză trebuie să fie foarte înalt, deoarece arborele de analiză nu poate genera foarte multe -- nu se poate extinde foarte mult la fiecare nivel. Deci ne vom uita la cât de mult se poate extinde. Dar depinde de gramatică, cât de multă expansiune au la fiecare nivel. Și va fi... nu poți avea doar în trei niveluri o mică gramatică care generează un șir de lungime de 1 milion. Vei vedea că e imposibil. Așa că, odată ce știi că arborele de analiză este cu adevărat înalt aici, atunci de fapt ai terminat, pentru că ce înseamnă să fii cu adevărat înalt? Înseamnă că există o cale care începe de la variabila de pornire E, o numesc în acest arbore de analiză, care coboară până la un simbol terminal în s, care trece prin mulți pași. Asta înseamnă ca copacul să fie foarte înalt. Și fiecare dintre acești pași este o variabilă până când ajungi până la capăt. OK, așa arată copacii analizați. Continuați să extindeți variabilele până ajungeți la un terminal. Deci aici, veți obține o cale care este într-adevăr o cale lungă. Și odată ce aveți o cale lungă care are multe, multe variabile care apar aici, ei bine, gramatica în sine are doar un număr fix de variabile în ea, așa că va trebui să aveți o repetare între variabilele care apar pe acea cale lungă. Am inteles? Deci, un șir lung forțează un arbore de analiză înalt, forțează o repetiție pe o cale care iese din variabila de început a unei alte variabile care iese. Acum asta ne va spune cum să tăiem s, pentru că dacă te uiți la subarborele lui s pe care le generează acele două variabile R , afișate astfel, voi folosi asta-- așa că trebuie să urmezi ceea ce am" spun eu aici. Deci R aici generează această porțiune a s. Și R inferior generează o porțiune mai mică de s, doar privind subarborele pe care îl obțineți aici. Și asta ne va spune că putem tăia s în consecință. Deci u a fost acea primă parte generată de E, dar nu de primul R. R este generat - v este generat de primul R, dar nu de al doilea R. Al doilea R generează exact x. Și apoi avem y și z, în mod similar. Așa că totul rezultă din a avea un arbore de analiză înalt. Și acum am terminat. Acum știm cum să tăiem s. De unde știm că putem repeta v și y și să fim în continuare în limbă? Ei bine, vă voi arăta de fapt că sunteți în limbă expunând un arbore de analiză pentru șirul uvvxyyz. Iată-l. Voi obține acel arbore de analiză , când extind acest R inferior, în loc să îl extind pentru a obține x, voi urma aceleași substituții pe care le-am avut atunci când am extins R superior. Deci, parcă aș fi am luat acest subarbore mai mare aici și l-am înlocuit cu subarborele mai mic de sub al doilea R. Și așa am obținut o imagine care arată așa. Așa că aici înlocuiesc sub al doilea R același subarbore pe care l-am avut inițial din R superior, primul R. Și așa că acum acest arbore de analiză generează șirul uvvxyyz, care este ceea ce caut. Și, desigur, poți face asta din nou și din nou. Și veți continua să obțineți exponenți din ce în ce mai mari pentru v și y. Și, de fapt, puteți obține chiar și exponentul 0, ceea ce înseamnă că v și y dispar cu totul. Și pentru asta, faci ceva ușor diferit, și anume că înlocuiești subarborele mai mare cu subarborele mai mic . OK, deci aici, care inițial a fost acel arbore mai mare care genera vxy, am lipit în schimb subarborele mai mic. Eu fac înlocuirile din subarborele mai mic. Și am ajuns la x acolo. Și deci acum șirul pe care l-am generat este uxz, care este același cu uv la 0 xy la 0 z. Și asta este ideea dovezii. Acum, cred că ați putea determina cantitățile de care aveți nevoie pentru a conduce această dovadă. O să fac asta pentru tine. De fapt, urăsc să scriu multe inegalități, ecuații și așa mai departe, pe tablă, pentru că cred că sunt aproape de neînțeles de urmat. Sau cel puțin ar fi pentru mine. Dar o să le pun acolo doar de dragul completității. Deci aici vom oferi detaliile acestei dovezi pe următorul diapozitiv aici. Da, așa că vreau doar să-i dau un nume. Voi numi asta argumentul de tăiere și lipire, pentru că decupez bucăți din acest arbore de analiză și le lip în alte locuri din arborele de analiză pentru a obține șiruri noi care sunt generate. Deci, acesta este un argument de tăiere și lipire. Deci, OK, să aruncăm o privire la detaliile de aici, doar, ei bine, trebuie să înțelegem, ei bine, cât de mare trebuie să fie de fapt p pentru ca acest lucru să intre? Ei bine, în primul rând, trebuie să înțelegem cât de repede poate crește acel arbore de analiză pe măsură ce mergem de la un nivel la altul. Și asta va depinde de cât de mari sunt părțile drepte ale regulilor. Adică, asta chiar îți spune câte... care este ventilatorul pe care îl cunoști despre fiecare nod? Care este ventilația maximă? Și aceasta va fi lungimea maximă a unei părți din dreapta a oricărei reguli. Deci, de exemplu, în acea altă gramatică pe care o văzusem ultima dată pentru expresii aritmetice, aveam că acest E merge la E plus T, această regulă aici. Și în ceea ce privește arborele de analiză, ar arăta ca un mic element ca acesta. Și asta este de fapt cea mai lungă parte dreaptă pe care o poți obține. Și astfel arborele de analiză poate crește cu un factor de 3 de fiecare dată. Acum, asta ne va spune cât de mare trebuie să fie șirul care este generat, care este valoarea lui p pentru a obține un arbore de analiză suficient de mare, astfel încât să obțineți o variabilă repetată. Să numim înălțimea arborelui de analiză pentru S h. Deci acum, dacă tu... asta doar repet ceea ce tocmai am spus. Dacă aveți un arbore de înălțime h și ramificarea maximă este b, atunci obțineți, cel mult, b la frunzele h, pentru că la fiecare nivel, obțineți un alt factor de b, pentru că atâta ramificare aveți. Deci fiecare nod de la un nivel poate deveni b noduri la nivelul următor în jos. Deci înmulțiți cu b de fiecare dată. Și dacă aveți niveluri h, veți avea b până la h frunze. Deci lungimea lui s, care sunt de fapt frunzele aici, este de cel mult b la h. Motivul pentru care este cel mult și nu exact este că s-ar putea să faci unele înlocuiri care sunt mai scurte pe partea dreaptă. OK, deci pentru a încerca să arătăm asta ca o imagine aici, trăgând aceeași imagine pe care o aveam înainte, vrem ca h, înălțimea, să fie mai mare decât numărul de variabile pentru a forța o repetare. Deci numărul de variabile va fi scris în acest fel. V este variabilele. V cu bare în jurul lui va fi numărul de variabile. Și vrem ca acea înălțime să fie mai mare decât numărul de variabile. Deci, odată ce știi cât de înalt vrei să fie acel copac pentru a forța o repetare, atunci îți spune cât de mare trebuie să fie s. Deci V trebuie să fie mai mare decât b la V, b la dimensiunea lui V, pentru că atunci înălțimea pe care o veți obține va fi mai mare decât dimensiunea lui V, care este... deci asta doriți . Vrei ca h să fie mai mare decât dimensiunea lui V. Așa că vei seta p ca să fie cu unul mai mult decât b față de V. Și deci, dacă s este cel puțin aceeași lungime, toată chestia asta va începe. Și veți obține acea variabilă repetată. Deci, vom lăsa p să fie acea valoare în care V este numărul de variabile din gramatică. Și deci, dacă s este cel puțin p, care este mai mare decât b la V, atunci lungimea lui s va fi mai mare decât b la V. Deci h va fi ceea ce doriți ca acest lucru să funcționeze. Dacă nu urmați asta, acele inegalități, vă simpatizez. Niciodata nu as urma asta intr-o prelegere. Deci, dar sper că înțelegeți ideea. Dar nu am terminat încă, pentru că vreau să mă întorc acum și să mă uit la aceste trei condiții și să mă asigur că le-am capturat pe toate, pentru că, de fapt, nu este total evident în fiecare dintre acele cazuri că am" le-am luat. Deci, trebuie să facem câteva lucruri suplimentare. OK, deci aceasta este concluzia argumentului. Vor fi cel puțin V plus 1 variabile pe calea cea mai lungă . Deci va fi o repetare. Deci acum să ne întoarcem aici și să vedem, acum că avem această imagine cu o variabilă repetată, de unde știm că putem obține condiția unu? Ei bine, acesta este doar argumentul de tăiere și lipire din slide-ul anterior. De unde știm că v și y nu sunt ambele goale? Ei bine, de fapt, asta nu este total evident, pentru că este posibil ca, atunci când ați generat v aici și ați generat y, poate trecând de la acest R la acel R, să nu aveți nimic nou. Știi, ar fi putut fi ca R să fi fost înlocuit cu T, o altă variabilă fără a ieși nimic nou, iar apoi T a fost înlocuit cu R. Ai înlocuit T cu R și apoi R cu T. Și nu ai ieșit nimic nou . Și în acest caz, v și y ar fi ambele șirul gol. Și asta ar încălca ceea ce ne dorim. Modul în care te deplasezi... asta și acestea sunt detalii aici. Dacă nu respectați în totalitate aceste puncte, nu vă faceți griji. Sunt ușor de descris. Așa că îmi dau seama, permiteți-mi să prezint totul în detaliu. Deci, dacă trecerea de la acest R la acel R nu generează nimic nou, veți obține exact aceleași lucruri care ies -- v și y sunt doar șirul gol -- cum evităm să se întâmple asta? Există o modalitate simplă de a aborda acest lucru, și anume, dacă aveți acest șir de caractere, atunci când luați un arbore de analiză, asigurați-vă că luați un arbore de analiză cât mai mic posibil. Nu aveți voie să începeți cu un arbore de analiză ineficient care poate fi scurtat și totuși genera s. Vreau cel mai mic arbore de analiză posibil. Și cel mai mic arbore de analiză posibil nu poate avea un R care merge la un alt R care nu generează nimic nou, pentru că atunci ai fi putut oricând să eliminați acel pas. Și ați avea totuși un arbore de analiză pentru s, dar ar fi un arbore de analiză mai mic. Deci asta ar fi... Vreau să începi cu cel mai mic arbore de analiză posibil. Și apoi vi se va garanta că v sau y va fi ceva care nu este gol. Deci asta are grijă de condiția a doua. Condiția trei-- știi, de unde știm că vxy împreună nu este foarte lung? Și, în principiu, este același argument din nou. Vrei doar să te asiguri că, atunci când alegi repetarea R, cele două R aici, alegi cele mai mici repetări posibile care apar, dacă ai multe opțiuni. Și cele două mai mici, acele mai mici repetiții, nu va exista nicio repetiție mai mică aici. Și apoi, prin același argument, deoarece odată ce aveți primul R, nu mai există repetiții mai jos, vxy-ul nu poate fi foarte lung, deoarece asta ar forța, din nou, să apară o altă repetiție. Deci, oricum, acestea sunt cele trei condiții. Și aceasta este dovada lemei de pompare pentru h limbi libere. Să vedem cum îl folosim. OK, deci haideți să facem un exemplu de demonstrare a unei limbi care nu este lipsită de context folosind lema de pompare. Cum ai de gând să faci asta? Pentru că acesta este genul de lucru, cel puțin, trebuie să știi cum să faci asta pentru a face temele. Aș vrea să vă motivez că lucrurile sunt atât de interesante și distractive, dar nu funcționează pentru toată lumea. Așa că, pentru cei practici , fiți atenți ca să vă puteți face temele. OK, să ne întoarcem la limba aceea în care am avut câteva diapozitive înapoi, 0 la k, 1 la k, 2 la k. Nu este un limbaj fără context. Vom arăta că acum utilizând lema de pompare pentru limbaje fără context. Așa că se va descurca, similar cu dovezile folosite pentru limbaje neobișnuite, dovezi prin contradicție. Deci, mai întâi presupuneți că limbajul nu are context. Și apoi vom aplica lema de pompare. Și atunci vom obține o contradicție. Deci lema de pompare dă acea lungime de pompare, așa cum am descris mai sus. Și acum vrem doar să alegem un șir mai lung în limbă și să arătăm că acel șir mai lung, care ar trebui să fie pompabil și să rămână în limbă, de fapt nu este pompabil. Deci lema de pompare spune că o puteți împărți în cinci bucăți care să satisfacă cele trei condiții. Condiția a treia implică că... așa că acum o să trec . Am să arăt că ai o contradicție. Deci condiția trei implică faptul că nu puteți conține ambele 0 și-- să tragem o imagine aici. Deci aici sunt s, 0, 1 și apoi 2, toate de aceeași lungime. Condiția trei - așa că dacă o despărți, condiția trei spune că vxy împreună nu poate fi prea lung. Ei bine, dacă vxy împreună nu este prea lung, cum s-ar putea ca, când repeți v și y, să rămâi în limba? În primul rând, nu puteți avea 0, 1 și 2 care apar în v, x și y. Un simbol va fi omis. Așadar, atunci când vei pompa, vei avea un număr inegal de simboluri. Și așa vei fi în afara limbii. OK, deci indiferent cum ai încerca să-l tăiați urmând condiția a treia, care este unul dintre lucrurile care limitează modalitățile de a-l tăia, veți ajunge, atunci când veți pompa, să ieșiți din limbaj. Și, prin urmare, nu este în... D? D greșește. B, ar trebui să spună „B”. Ar trebui să pot scrie despre chestia asta. Cred ca nu. Nu am testat asta. Ei bine, acesta ar trebui să fie un B. Deci B este un limbaj fără context , care include-- deci aceasta este presupunerea că B este un limbaj fără context. Asta e fals. Și tragem concluzia că nu este un limbaj fără context. Hai să facem... oh da, am un control aici. Deci haideți să vedem la ce vă voi cere să vă gândiți. OK, capul meu blochează o parte din text? Oh, asta a fost acum ceva vreme. Da, deci, apropo, doar o întrebare, în ceea ce privește aplicarea lemei de pompare - fie v, fie y pot fi goale, dar nu ambele. Dar oricum, să trecem la acest check-in aici. Deci, să ne uităm la aceste două limbi, A1 și A2, care arată foarte asemănătoare cu B, dar puțin diferite. Deci, A1 este 0 la k, 1 la k, 2 la l, unde k și l pot fi orice numere, orice numere pozitive, nenegative. Deci, practic, ceea ce spune asta este că numărul de 0 și 1 va fi egal, dar numărul de 2 poate fi orice, în timp ce A2, similar, dar aici, solicităm ca numărul de 1 și 2 să fie egal. . Iar numărul de 0 poate fi orice. Acum, poți să faci cu ușurință, sper... ar trebui să te asiguri că poți... automate pushdown care pot recunoaște A1 și A2, pentru că să luăm doar A1. Automatul pushdown poate împinge 0-urile în timp ce le citește, le poate trage în timp ce citește 1-urile pentru a le potrivi și să se asigure că sunt același număr dintre ele. Și apoi cei 2, nu-i pasă câți sunt. Trebuie doar să se asigure că nu există șiruri, că nu există litere care nu ies din ordine. Dar orice număr de 2 este bine. Deci, puteți face cu ușurință un automat pushdown care recunoaște A1, în mod similar pentru A2. Deci, ce putem concluziona din asta? Iată cele trei posibilități. Permiteți-mi... deci uită-te la asta, clasa de limbi fără context nu este închisă sub intersecție. Îl poți citi. Așa că vreau să ridic sondajul și să lansez asta. Vă rugăm să completați asta. 10 secunde. Din nou, doar, dacă nu cunoașteți răspunsul, dați orice răspuns, astfel încât... pentru că nu numărăm corectitudinea. Mai sunt câteva driblinguri. OK, cinci secunde. OK, termină sondajul. Majoritatea dintre voi au avut dreptate. Nu știu. Este în regulă să împărtășești aceste lucruri? Nu vreau să-i fac pe cei care nu au primit ce trebuie să se simtă rău. Știi, dar ar trebui să înțelegi, cred că dacă îți lipsește ceva, ar trebui să înțelegi ce îți lipsește. Lema de pompare arată că uniunea A1 A2 nu este un limbaj fără context? Nu. După cum am menționat la început, limbile fără context sunt închise sub unire. Deci, lema de pompare ar fi mai bine să nu arate că acestea-- știm deja că aceste două limbi sunt fără context, pentru că le obținem de la automatul pushdown. Și am spus la început că limbajul fără context este închis sub unire. Așa că știm că aceste două sunt fără context. Deci, lema de pompare ar fi bine să nu arate că nu sunt lipsite de context. Ceva ar fi îngrozitor... ar fi mers teribil de prost dacă ar fi adevărat. Și, de asemenea, știm și dintr-un pic de raționament suplimentar că limbile fără context nu sunt închise în completare cu ceea ce am discutat deja, pentru că sunt închise sub unire. Și după cum am subliniat, nu sunt închise sub intersecție. Și deci, dacă ar fi închise sub complement, legile lui De Morgan ar spune că închiderea sub unire și închiderea sub complement ți-ar da închidere sub intersecție. Dar nu avem închidere sub intersecție. Deci, de fapt, ele nu sunt închise sub complement. OK, deci, de fapt, acest lucru ne arată că clasa de limbaj fără context nu este închisă sub intersecție, deoarece intersecția dintre A1 și A2, două limbaje fără context, este B. Și B nu este liberă de context. Deci arată că aceasta este... închiderea sub intersecție nu se menține. Deci haideți să continuăm, atunci. Mai avem un exemplu. Atunci vom face o pauză. Deci, lema de pompare pentru limbaje fără context, din nou, iată al doilea exemplu. Iată limbajul F. Am mai văzut asta înainte. ww, două copii ale unui șir, două copii ale oricărui șir -- și vom arăta că nu este un limbaj fără context. Să presupunem că nu are context , lema de pompare dă lungimea de pompare. Acum, aici trebuie să lucrați puțin mai mult. Adesea, provocarea în aplicarea lemei de pompare în oricare dintre cazurile pe care le-am văzut implică alegerea acelui șir pe care trebuie să îl pompați, pe care îl veți pompa. Deci, trebuie să alegeți s în F, care este mai lung decât p, cu care s se potrivește. Așa că s-ar putea să-l încerci pe acesta , la prima vedere. Iată un șir care este în limbaj, pentru că sunt două copii ale șirului 0 la p1 0 la-- și apoi 0 la p1. Deci asta e în limbaj, dar este o alegere proastă. Înainte de a trece înaintea mea, haideți să facem o imagine a lui s, pe care cred că este întotdeauna util să văd. Așadar, aici sunt runde de 0 și apoi 1, runde de 0 și apoi 1. De ce este aceasta o alegere proastă? Pentru că poți pompa acel șir și rămâi în limbaj. Există o modalitate de a tăia sfoara aceea și vei rămâne în limba. Și modalitatea de a-l tăia este să lași x să fie doar acel subșir care este doar 1. Și v și y pot fi câteva 0 sau un singur 0 de fiecare parte a acelui 1. Și acum asta va fi un mic vxy. Dar dacă repeți v și y, vei rămâne în limba, pentru că vei adăuga doar 0 aici. Veți adăuga același număr de 0 acolo. Și apoi vei avea un șir care încă arată ca ww. Și vei fi în continuare în limbă. Deci asta înseamnă că tăierea lui nu te scoate din limbaj sub pompare. Și adevărul este că aceasta este o alegere proastă pentru s, pentru că există acel mod de a o tăia. Așa că trebuie să arăți că nu ai cum... nu poți alege calea de a o tăia. Trebuie să arăți că nu există nicio modalitate de a-l tăia pentru a încălca lema de pompare. Deci, dacă în schimb folosiți șirul 0 la p, 1 la p, 0 la p, 1 la p-- deci acesta este 0 urmat de 1 urmat de 0 urmat de 1, toate același număr de ele-- care nu poate fi pompat îndeplinind cele trei condiții. Și doar trecând prin asta... acum, dacă încerci să o rupi, vei pierde. Sau lema va pierde. Vei fi fericit, dar lema nu va fi fericită, pentru că nu va merge-- va încălca condiția. Condiția trei spune că vxy nu este-- nu se întinde prea mult și, de fapt, nu poate cuprinde două serii de 0 sau două secțiuni de 1. Pur și simplu nu este suficient de mare, pentru că sunt mai mult decât p lucruri... sunt p lucruri aparte. Și acest șir, acest șir vxy este doar p lung. Prin urmare, dacă repeți v și y, veți avea două runde de 0 sau două 1 care au lungime inegală. Și acum aceasta nu va fi forma ww. Vei fi în afara limbii. Așa că sper că asta e... ai puțină practică cu asta. Cred că suntem la pauză. Și ne vedem aici în cinci minute, dacă îmi pot lansa cronometrul aici. OK, așa că ne vedem curând. Apropo, acesta este un moment bun pentru a trimite mesaje mie sau AT. Și voi încerca să caut dacă aveți întrebări. În lema de pompare, poate x-- da, x poate fi epsilon în lema de pompare. x poate fi epsilon. y poate fi epsilon, dar x și y nu pot fi ambele epsilon, pentru că atunci, atunci când pompați, nu veți obține nimic nou. Din punct de vedere tehnic, v și y pot include atât 0, cât și 1. Da, v și y pot include atât 0, cât și 1. Așa că, permiteți-mi să încerc să pun asta înapoi, dacă asta este voință-- deci v și y pot avea atât 0, cât și 1, dar nu pot avea 0 din două blocuri diferite. Și nu poți avea 1 din două blocuri diferite. Deci, ceea ce se va întâmpla este fie că vei pune lucrurile în ordine când repeți - cum ar fi, un v are atât 0, cât și 1 în el. Când repeți v, vei avea 0 și 1, și 0 și 1 și 0 și 1. Este clar în afara limbajului, așa că nu e bine. Singura ta speranță este să ai v să se lipească numai în interiorul lui 0 și y să se lipească doar în interiorul lui 0 sau doar în interiorul lui 1. Dar acum, dacă repeți asta și doar te uiți la ce vei obține, vei avea un șir care va fi... dacă încerci să tai acel șir în jumătate, nu va fi de forma potrivită. Nu vor fi două copii ale aceluiași șir, deoarece va avea o serie de 0 urmată de o serie mai lungă sau mai scurtă de 0, sau o serie de 1 urmată de o altă serie de 1 de lungime inegală. Deci, nu există nicio modalitate de a putea fi două șiruri, două copii ale aceluiași șir, pentru că asta ai nevoie. F trebuie să fie două copii ale aceluiași șir pentru a fi în limbă. Bine, lasă-mă să văd unde... rămânem fără timp aici. Lasă-mă să-mi pun cronometrul aici. Avem doar 30 de secunde. Și îmi pare rău că nu apuc să răspund la toate întrebările de aici. OK, am terminat cu pauza. O să se întoarcă. Și acum schimbăm vitezele într-un mod major, pentru că, într-un fel, tot ce am făcut până acum a fost un fel de încălzire. Aceste modele de calcul limitate ne ajută într-adevăr să ne stabilim înțelegerea automatelor, a definițiilor și a notației. Și vor fi, de asemenea, de ajutor pentru a oferi exemple mai târziu în termen. Dar, într-adevăr, în ceea ce privește un model de calcul, ei nu îl reduc, pentru că nu pot face lucruri foarte simple pe care în mod normal credem că un computer este capabil să le facă. Așa că aici introducem un alt model de calcul, numit mașina Turing. Și acesta va fi într-adevăr modelul cu care ne vom menține pentru restul semestrului, pentru că acesta va fi modelul nostru de computer de uz general, așa cum vă gândiți în mod normal la asta. Deci hai să... vom petrece puțin timp prezentându-l. Și apoi vom continua discuția data viitoare. Deci, din punct de vedere al unei scheme, de fapt, modelul mașinii Turing este destul de simplu. Va avea state și toate chestiile astea. Deci va exista un control finit aici, care va include stări și o funcție de tranziție, așa cum vom descrie într-un minut. Ideea este că intrarea va apărea pe o bandă. Diferența cheie acum este că aparatul va putea schimba simbolurile de pe bandă. Și așa ne gândim la mașină ca fiind capabilă să scrie și să citească caseta. Deci, aceasta este cu adevărat caracteristica cheie a unei mașini Turing, este capacitatea de a scrie pe bandă. Orice altceva, într-un sens, decurge din asta și alte câteva diferențe. Dar, deci, faptul că capul poate citi și scrie, astfel încât să putem folosi banda ca spațiu de stocare la fel cum folosim teancul de stocare, dar nu este limitat în modul în care îl putem accesa așa cum este o stivă -- așa că am amabil au acces foarte flexibil la informațiile de pe bandă. Acum, posibilitatea de a scrie pe bandă nu face niciun folos dacă nu poți să te întorci și să citești ce ai scris mai târziu. Așa că vom face capul pentru a putea fi în două sensuri. Deci capul se poate mișca de la stânga la dreapta ca înainte, dar se poate deplasa și înapoi la stânga. Și asta va fi sub controlul funcției de tranziție, deci sub controlul programului, în esență. Caseta va fi... hopa, scuze. Banda este infinită la dreapta. Și astfel nu vom limita spațiul de stocare pe care îl poate avea mașina. Deci banda va avea... ne vom gândi ca având, în loc să aibă doar intrarea pe ea, va avea intrarea. Dar apoi restul, va avea infinit de spații libere, simboluri goale după intrare. Deci banda este infinită în direcția din dreapta. Și astfel există o infinitate de spații libere. Voi folosi acel simbol pentru ca spațiul liber să urmeze intrarea. Puteți accepta sau respinge. Da, deci ăsta e un alt lucru important. În mod normal, ne gândim la -- în mașinile anterioare, automate finite, automate pushdown, când ați ajuns la sfârșitul intrării, atunci a fost decisă acceptarea sau respingerea. Dacă urma să-l acceptați la sfârșitul introducerii, atunci ați acceptat. Dar trebuie să fii în acea locație la sfârșitul introducerii pentru ca aceasta să aibă efect. Asta nu mai are sens, pentru că aparatul s- ar putea să se oprească dincolo de asta și să continue să calculeze și să se întoarcă și să citească caseta mai târziu. Așa că are sens doar să lăsați mașina să accepte sau să respingă la intrarea în starea de acceptare sau respingere. Deci vom avea o stare specială de acceptare și o stare specială de respingere , care este, de asemenea, puțin diferită față de înainte. Și când mașina intră în acele stări, atunci mașina... atunci acțiunea are efect. Aparatul se oprește și apoi acceptă sau se oprește și apoi respinge. Așa că vom face acest lucru absolut clar în definiția formală într-o secundă, dar doar pentru a înțelege spiritul acesteia. Așa că am să vă dau un exemplu de lucru care rulează. Îmi pare rău, și eu... din nou, PowerPoint-ul meu are probleme. OK, deci iată o mașină Turing care recunoaște acea limbă b. De fapt, ți-am schimbat treptele. În loc de 0, 1 și 2, le-am făcut a, b și c, dar aceeași idee. Așa că o să vă arăt cum funcționează mașina Turing. Și apoi vom da o definiție formală. Sper că asta este aici. Cred că este. Într-o secundă, dar haideți-- aceasta este o discuție informală despre cum va funcționa mașina pentru a face acest limbaj, a la k, b la k, c la k, folosind capacitatea sa de a scrie pe bandă ca precum și să citească și să-și miște capul în ambele direcții. OK, așa că permiteți-mi să descriu mai întâi în engleză cum funcționează această mașină. Și apoi îl vom vedea în acțiune pe această poză mică pe care o am aici. Așadar, modul în care va funcționa mașina este primul lucru pe care capul va începe aici. Și capul va scana spre dreapta, asigurându-vă că simbolurile apar în ordinea corectă. Deci este să vezi că există a și b și apoi c, fără a verifica cantitățile, doar că ordinea este corectă. Pentru asta, nu trebuie să scrii. Un automat finit poate verifica dacă intrarea este de forma a stea, b stea, c stea. Deci scrisul nu este necesar. Mașina, dacă detectează simboluri nefuncționale, respinge imediat trecând într-o stare specială de respingere. În caz contrar, își va întoarce capul înapoi la capătul stâng. Și permiteți-mi doar să arăt asta aici. Deci iată... oh, nu. Înainte să-l ilustrez aici, să parcurgem întregul algoritm. Deci următorul lucru care se întâmplă este că vei scana corect. Și acum vrei să faci numărătoarea. Așa că veți scana corect din nou, dar de data aceasta, veți face o grămadă de treceri peste intrare, o grămadă de scanări. Și de fiecare dată când faceți o scanare, veți tăia câte un simbol de fiecare tip. Așa că vei tăia un a. Vei tăia un b. Vei tăia un c la o singură scanare. Și apoi repeți asta, tăind următorul a, următorul b, următorul c. Și doriți să vă asigurați că ați tăiat toate simbolurile din aceeași rundă și că nu ați tăiat unele simboluri înaintea altor simboluri, în timp ce alte simboluri vor rămâne, deoarece asta ar însemna că numărările nu au fost egale. Dacă le tăiați și toate sunt epuizate la aceeași scanare, aceeași trecere, atunci știm că numerele trebuiau să înceapă să fie egale. Așadar, asta e un fel de chestii pentru bebeluși aici, dar sper că înțelegi ideea. Și o să ilustrăm într-o secundă. Dacă aveți ultimul din fiecare simbol - deci ceea ce vreau să spun prin asta este că tocmai ați tăiat ultimul a, ultimul b și ultimul c - atunci că ați avut inițial un număr egal. Și așa accepți, pentru că taci câte unul din fiecare la fiecare scanare. Deci, dacă bifați, la ultima scanare, fiecare dintre ele este tăiat, atunci acceptați. Dar dacă a fost ultimul simbol al unui simbol, dar nu al altor simboluri, deci ai tăiat ultimul a, dar au mai rămas câteva b, atunci ai început cu un număr inegal de a, b și c. Atunci poți respinge. Sau dacă toate simbolurile rămân încă după ce le-ați încrucișat, câte unul pe fiecare dezactivat, atunci nu ați făcut suficiente pase. Și vei repeta din etapa a treia și vei face asta din nou o altă scanare. OK, deci iată o mică animație care arată acest lucru pe această diagramă. Așadar, iată prima etapă în care scanați, asigurându-vă că lucrurile sunt în ordinea corectă. Nu a trebuit să scriu pe bandă. Și acum vei reseta capul înapoi la început. Apropo, aceasta nu este cea mai eficientă procedură pentru a face acest lucru. Acum vom face o scanare între un singur a, un singur b și un singur c. Deci aici, voi arăta că aici, un singur a, un singur b, un singur c. Și acum, de îndată ce ați tăiat ultimul c, ne putem întoarce la început. Așadar, scanați direct -- așa că dacă toate simbolurile rămân, deci mai rămân simboluri de fiecare tip, ne vom întoarce la stânga și vom repeta. Acum primim o altă trecere, single a, single b, single c sunt tăiați. Le-am tăiat încă pe toate? Nu, există... de fiecare tip, mai sunt altele. Deci, din nou, ne întoarcem la început. Acum avem o ultimă trecere, tăiați ultimul a, ultimul b, ultimul c. Ultima din fiecare tip a fost tăiată. Deci acum știm că putem accepta, pentru că șirul original era în limbaj. OK, asta pentru a vă oferi măcar o idee despre cum poate funcționa mașina Turing, mai mult ca modul în care v-ați gândi la funcționarea unui computer. Poate că este foarte primitiv. Vă puteți imagina și numărați. Și o mașină Turing poate conta, de asemenea. Dar aceasta este cea mai simplă procedură pe care ți-o pot descrie fără să o complic prea mult. OK, deci hai să verificăm puțin asta. OK, deci cum descriu asta, cum crezi? Și, într-un fel, încă nu știi destul. Dar cum crezi că vom obține acest efect de a întrerupe mașina Turing? Vom obține asta schimbând modelul și adăugând acea abilitate de a trece la model? Vom folosi un alfabet de bandă care include acele simboluri tăiate printre ele? Sau vom presupune doar că toate mașinile Turing vin cu o radieră și pot oricând să taie lucruri. Așadar, care crezi că este modalitatea plăcută, într-un fel matematic, de a descrie această abilitate de a tăia lucrurile? Da, din nou, majoritatea dintre voi, din nou, cred că primiți asta. Așa că sunt 10 întârziați aici. Așa că vă rugăm să finalizați, astfel încât să putem închide sondajul. Mai sunt cinci secunde. OK, sondajul se termină, primește ultimul... ultimul apel. Bine, împărtășește rezultatele. Deci majoritatea dintre voi au avut dreptate. Toate aparatele Turing vin cu radiera... Nu știu. Asta a fost aruncat acolo ca o glumă, dar a ajuns pe locul al doilea. Așa că nu te simți rău dacă ai primit-o, dar nu asta am avut în minte. Modul în care mașina Turing va scrie pe bandă este să scrie un simbol tăiat în loc de simbolul care era inițial acolo. Așa că vom adăuga aceste noi simboluri tăiate. Și acesta va fi un lucru obișnuit pentru noi când proiectăm mașini Turing. Nu vom ajunge la nivelul de implementare pentru foarte mult timp. Vom trece foarte repede la un nivel mai înalt de discuție despre mașini. Dar oricum, așa ați proceda dacă ați construi efectiv o mașină. Deci, să ne uităm la definiția formală. Și personal, poate că ar fi trebuit să fac acest check- in după definiția formală. S-ar putea să fi fost mai clar, dar ei bine. OK, Turing... iată definiția formală. De data aceasta, o mașină Turing este un tuplu de 7. Și există... acum aici, avem sigma, care este alfabetul de intrare. Gamma este alfabetul benzii. Deci acum sunteți puțin analog cu stiva de înainte, unde gamma era alfabetul stivei. Dar acestea sunt simbolurile pe care ai voie să le scrii pe bandă... care au voie să fie pe bandă. Deci, evident, toate simbolurile de intrare sunt printre simbolurile casetei, deoarece pot apărea pe bandă. Deci aveți sigma este un subset de gamma. Un lucru pe care nu l-am menționat aici este că alfabetul de intrare, nu permitem ca simbolul gol să fie în alfabetul de intrare, astfel încât să puteți utiliza de fapt simbolul gol ca delimitator pentru sfârșitul introducerii, un marker pentru sfârșitul intrării. Deci, de fapt, și simbolul gol va fi întotdeauna în alfabetul de bandă. Acesta va fi întotdeauna un subset adecvat din cauza simbolului gol. Dar doar permitem... nu prea contează. Permitem alfabetului de bandă să aibă alte simboluri pentru comoditate, de exemplu, aceste simboluri tăiate. Acum să ne uităm la ce funcție de tranziție, cum funcționează. Deci funcția de tranziție, amintiți-vă, spune modul în care mașina își face de fapt calculul. Și spune că, dacă ești într- o anumită stare și capul se uită la un anumit simbol pe bandă, atunci poți trece într-o stare nouă. Scrieți un simbol nou în acea locație pe bandă. Și puteți mișca capul fie la stânga, fie la dreapta. Așa obținem efectul ca capul să poată fi bidirecțional. Și iată scrierea de pe bandă. Apare chiar aici. Deci, doar un exemplu aici care spune că, dacă suntem în starea a doua și capul se uită la un a în prezent de pe bandă, atunci putem muta starea r. Schimbăm că a cu a b. Și mutam capul la dreapta 1 pătrat. Acum, acest lucru este important. Când dați o anumită intrare aici mașinii Turing, aceasta poate calcula pentru un timp, mișcându-și capul înainte și înapoi, așa cum am arătat. Și în cele din urmă s-ar putea opri fie prin intrarea în starea q accept sau în starea q resping, pe care nu am scos aici, dar asta este important. Acestea sunt stările speciale de acceptare, respingere ale mașinii. Sau este posibil ca mașina să nu intre niciodată într-una dintre acestea. Poate merge mai departe, și mai departe, și mai departe și să nu se oprească niciodată. Numim asta looping, un nume puțin greșit, deoarece looping implică un fel de repetiție. Pentru noi, bucla înseamnă pur și simplu să nu ne oprim. Prin urmare, M are trei rezultate posibile pentru fiecare intrare, aceasta w. S- ar putea accepta w prin intrarea în starea de acceptare. Ar putea respinge w intrând în starea de respingere, ceea ce înseamnă că îl va respinge prin oprire. Sau mai spunem că putem respinge prin loop. Puteți respinge șirul rulând pentru totdeauna. Aceasta este terminologia comună în materie. Așa că fie îl accepți oprindu-l și acceptând, fie respingându-l fie oprindu-se și respingând, fie pur și simplu mergând pentru totdeauna. Aceasta este, de asemenea, considerată a fi respingere, un fel de respingere într- un sens implicit. Dacă nu l-ați acceptat niciodată, atunci va fi respins. OK, faceți check-in trei aici... în regulă, așa că acum ultimul nostru check-in pentru ziua, spunem noi, acest model de mașină Turing este determinist. Eu doar spun asta. Dar dacă te uiți la modul în care am configurat-o, dacă ai urmat definiția formală până acum, ai înțelege de ce este deterministă. Deci, să vedem, ca o modalitate de a verifica asta, cum am schimba această definiție? Pentru că ne vom uita la următoarea prelegere la mașinile Turing nedeterministe. Deci, un pic de avans în asta, cum am schimba această definiție pentru a o face o mașină Turing nedeterministă? Pe care dintre aceste trei opțiuni am folosi? Deci aici, voi lansa acel sondaj. Mai am vreo 10 persoane. Să le mai dăm 10 secunde. OK, cred că sunt toți cei care au răspuns înainte. Deci aici, cred că aproape toți ați avut ideea corectă. Este B, de fapt, pentru că atunci când avem aici simbolul setului de putere , asta înseamnă că ar putea exista mai multe -- există un subset de posibilități. Deci asta indică mai multe moduri diferite de a merge. Și aceasta este esența non-determinismului. Bine, deci cred că suntem... hopa. Bine, așa că uite, asta ne pregătește și pentru următoarea prelegere și unde vom merge cu asta. Deci, acestea sunt practic două într-un-- ei bine, două sau trei definiții importante aici. Una este... am vorbit despre limbajele obișnuite din automatele finite. Am vorbit despre limbajele fără context din gramaticile și automatele pushdown. Care sunt limbajele pe care le pot face mașinile Turing? Acestea se numesc, în acest curs, oricum, limbi Turing-recognoscibile sau T recognoscibile. Acestea sunt limbile pe care mașina Turing le poate recunoaște. Și așa, doar pentru a ne asigura că suntem pe aceeași pagină în acest sens, limbajul mașinii este colecția de șiruri pe care mașina o acceptă. Deci lucrurile care nu sunt în limbă sunt lucrurile care sunt respinse fie prin buclă, fie prin oprire și respingere. Deci numai cele care sunt acceptate este limba. Fiecare mașină are doar o singură limbă. Este limba tuturor șirurilor de caractere pe care o acceptă mașina respectivă. Și vom spune asta și vom recunoaște acea limbă, dacă acea limbă este colecția de astfel de șiruri care sunt acceptate. Și vom numi acea limbă o limbă care poate fi recunoscută de Turing, dacă există vreo mașină Turing care o poate recunoaște. Acum, această caracteristică de a putea respinge alergând pentru totdeauna este puțin ciudată, poate. Și din punct de vedere practic, este mai convenabil dacă mașina ia întotdeauna decizia de a accepta sau de a respinge într-un timp finit și nu doar respinge mergând pentru totdeauna. Și așa vom scoate la iveală o clasă specială de mașini Turing care au această caracteristică, pe care o opresc întotdeauna. Stările de oprire, apropo -- poate că nu a spus acest lucru în mod explicit -- sunt stările q accept și q resping. Stările de acceptare și de respingere sunt stările de oprire. Deci, dacă mașina se oprește, înseamnă că ajunge într-una dintre cele două. Deci a luat decizia de a accepta sau de a respinge în momentul în care sa oprit. Așa că vom spune că o mașină este un decident dacă se oprește întotdeauna la fiecare intrare. Deci, pentru fiecare w introdus, mașina va ajunge în cele din urmă la un q accept sau un q resping. Numim o astfel de mașină un decident. Și acum vom spune, o limbă este... așa că vom spune că mașina decide o limbă dacă este limba mașinii, deci colecția de șiruri acceptate, iar mașina este hotărârea. Vom spune că, în loc să recunoaștem doar limba, vom spune că ea decide limba. Iar limbajul Turing-decidabil este un limbaj pe care mașina-- dintre toate șirurile de caractere pe care mașina le acceptă pentru o mașină Turing care este un decident, care este o mașină Turing care se oprește întotdeauna. Deci, dacă o mașină Turing poate respinge uneori prin buclă, atunci își recunoaște doar limbajul. Dacă mașina Turing se oprește întotdeauna, deci respinge întotdeauna, ajungând în mod explicit la o stare de respingere și oprindu-se, atunci vom spune că de fapt decide limba. Deci, într-un fel, așa e mai bine. Și vom face distincția între cele două, pentru că nu sunt la fel. Există unele limbi care pot fi recunoscute, dar nu decise. Și, de fapt, vom obține următoarea imagine aici, că limbajele recunoscute de Turing sunt un subset adecvat. Ele includ toate -- tot ceea ce este decidabil, cu siguranță va fi recunoscut, pentru că a fi un decident este o restricție suplimentară de impus, o cerință suplimentară. Deci tot ceea ce este decidabil va fi recunoscut automat. Dar există lucruri care sunt recunoscute și nu sunt decidabile, după cum vom vedea. De fapt, voi da un exemplu în acest sens, dar nu îl voi dovedi la următoarea prelegere. Și doar pentru a completa această imagine, voi sublinia, de asemenea, -- nu am dovedit încă acest lucru, dar o vom demonstra -- că limbile determinabile includ și toate limbile fără context, care , la rândul său, includ limbile obișnuite, așa cum sa văzut deja. Deci nu am arătat încă această includere. Dar, de fapt, aceasta este imaginea pe care o obținem. Deci, există de fapt o ierarhie de izolare aici. Limbile obișnuite sunt un subset al limbilor fără context, care sunt, la rândul lor, un subset al limbilor determinabile, care, la rândul lor, sunt un subset al limbilor recunoscute de Turing. Și, cu asta, cred că vom trece la mica noastră recenzie a ceea ce am făcut astăzi. Așa că am demonstrat că pomparea lemei ca instrument pentru a arăta că limbile nu sunt limbi fără context. Am definit mașinile Turing, care va fi modelul nostru pe care ne vom concentra pentru tot restul termenului, fără a uita celelalte modele, pentru că vor fi exemple utile pentru noi. Și am definit decizii Turing, dispozitivele de decizie Turing care se opresc pe toate intrările. OK, deci cred că, cu asta, am ajuns la sfârșitul prelegerii de astăzi. Voi rămâne puțin și voi răspunde la întrebări în chat. Voi încerca să le împărtășesc tuturor pe măsură ce le răspund, astfel încât să nu vorbesc doar cu o singură persoană. Cum se aplică conceptul în... așa că primesc o întrebare despre caracterul practic al tuturor acestor lucruri. Urmează o grămadă de întrebări . Deci uite, toate lucrurile astea sunt practice? Aș spune, da și nu. Nu știu ce concept ai în minte. Vom introduce o mulțime de concepte în acest curs. Și conceptul de automată finită și automată pushdown și limbaje fără context , utilizate cu siguranță în alte discipline, în alte domenii ale informaticii și în alte părți - acestea sunt noțiuni foarte de bază și fundamentale. Și așa da, și mașinile Turing... ei bine, vreau să spun că este un model de computer general. Dacă doriți să înțelegeți calculul, va trebui să înțelegeți un model. Și o mașină Turing este un model deosebit de simplu. Și de aceea îl folosim. După cum se dovedește, nu contează cu adevărat ce model folosești, dar despre asta vom vorbi data viitoare. Dar da, aș spune că există o mulțime de material aplicat în acest curs, după cum a arătat timpul, fie că a condus la lucruri precum criptografia cu cheie publică, care este folosită pe internet, sau înțelegerea diferiților algoritmi. Adică, nu acesta este motivul pentru care îl studiez. Îl studiez pentru că mă gândesc mai mult la asta dintr-o perspectivă mai mult matematică. Pur și simplu găsesc materialul foarte frumos, interesant și provocator, dar are aplicații. Alte întrebări aici? Cred că mă voi deconecta, atunci, pentru a mă configura pentru programul meu de birou, care se află pe un alt link Zoom. OK, așa că mulțumesc tuturor. Și ne vedem joi. Pa! Pa.