bine, de ce nu începem, salut tuturor, vedeți câți am ajuns aici, majoritatea dintre voi, sunt sigur că ceilalți vor apărea, sper că uh, destul de curând, așa că bine ați revenit, avem prelegerea de azi patru și să ne amintim doar ce am" Am făcut-o în ultimele câteva prelegeri, am explorat limbajele obișnuite, așa cum sunt descrise de automate finite și expresii regulate, am arătat cum să le convertim înainte și înapoi acele două modele unul la altul și am arătat, de asemenea, cum să demonstrăm că anumite limbi nu sunt obișnuit, acum amintiți-vă că automatele finite sunt un model de calcul foarte slab, au doar o memorie limitată, o memorie finită și încă nu sunt capabili să facă anumite lucruri cu memoria lor finită, dar știți dacă le comparați. cu un computer de uz general, cel puțin modul în care ne gândim la el este, uh, știi că capacitățile lor sunt extrem de limitate și, așa că, în următoarele câteva prelegeri, vom explora câteva modele mai puternice pe care am început să le facem ultima dată. uh gramaticile fără context și, după cum vom vedea, există anumite lucruri pe care le puteți face, cred că am văzut că și ultima dată, acestea sunt câteva lucruri pe care le puteți face cu gramatici fără context pe care nu le puteți face cu automate finite și uh dar ele încă au limitările lor, așa cum vom vedea astăzi, ceea ce vom face, vom continua acea discuție, uitând la definiția gramaticilor fără context într-un mod mai formal, uh, unul dintre Lucrurile pe care le facem în acest curs sunt să dezvoltăm exersarea cu formalism și, astfel încât asta să fie în spiritul acestuia, ne vom uita și la limbile asociate, numite limbi libere de context, așa că vor fi omologul pentru gramaticile fără context a ceea ce sunt limbajele obișnuite pentru automatele finite ale expresiilor regulate și apoi ne vom uita la un model bazat pe un automat care este omologul gramaticilor numite automate push down și vom vedea că acestea sunt echivalente în putere și, în cele din urmă, bine și, ca parte a acesteia, vom arăta cum să convertim gramaticile fără context în automatele push-down și asta este ceea ce vom face astăzi, așa că vom face treceți apoi și reveniți la subiectul nostru despre gramatici fără context pe care l-am început data trecută și doar pentru a vă reîmprospăta memoria, așa că iată acel exemplu de gramatică fără context pe care am dat-o data trecută și are felul în care suntem Vom scrie gramatici fără context folosește o scurtă scurtă, uh, care arată astfel, atunci când aveți mai multe reguli care au aceeași variabilă în partea stângă, le puteți combina într-o singură linie, astfel încât aceste două reguli de aici s merge la 0 s1 și s merge la r poate fi scris într-o singură linie, într-un mod puțin mai compact, acesta este standard, deoarece s merge la 0 s 1 sau r, acolo ați citi, acestea sunt de fapt două reguli, dar scrise pe una Linia bine, așa cum vă amintiți de ultima dată, o gramatică fără context are variabile terminale și reguli, uh, acestea sunt părțile despre care vorbim, precum și una dintre variabilele desemnate ca o variabilă de pornire care pune totul în mișcare Așa că o să vorbesc să vă reamintesc despre cum decurge calculul, dar um, deci variabilele sunt simbolurile care apar în partea stângă a regulilor, terminalele sunt celelalte simboluri care apar în gramatică și luăm gramatica și noi Folosește-l pentru a genera șiruri în conformitate cu un anumit sistem și sistemul este că începi prin a nota variabila de pornire și apoi, odată ce ai notat acea variabilă sau orice variabile pe care le-ai notat, ai voie să le înlocuiești în funcție de la regulile regulilor de substituție care sunt în gramatică, astfel încât să puteți continua să înlocuiți variabilele pe care le aveți cu părțile din dreapta corespunzătoare și apoi faceți asta din nou și din nou până când nu aveți variabile rămase doar simboluri terminale rămâne și în acel moment ați generat un șir care este în limba gramaticii în regulă, așa că limba gramaticală va fi o limbă peste șiruri al căror alfabet sunt simbolurile terminale, astfel încât simbolurile terminale într-un anumit sens joacă același rol ca și alfabetul de intrare spune pentru automatele finite, bine, variabilele sunt un fel de lucru intern, simboluri pentru gramatică, terminalele sunt un fel sunt simbolurile peste care este scris limbajul, bine, vom face asta mai precis într-un minut unde, atunci când dau definiția formală, rezultatul este șirul generat, iar limba gramaticii este limba tuturor șirurilor generate pe care le puteți obține folosind acea gramatică, deci, lucrul important este că numim acea limbă un limbaj fără context bine, așa că asta e ceea ce obținem din asta, este un lucru analog cu limbile obișnuite, dar aici le numim limbi fără context uh lucrurile pe care le poți obține dintr-o gramatică fără context din nou, doar o recapitulare rapidă a exemplului pe care l-am făcut ultima dată, așa că începeți prin a scrie variabila de pornire și apoi vă voi oferi un fel de două puncte de vedere despre aceasta, fie în ceea ce privește arborele de substituții pe care îl numim arborele de analiză, fie în ceea ce privește șirul rezultat așa cum faceți dvs. substituțiile, deci aici este arborele de analiză uh, aici este șirurile rezultate, aici sunt substituțiile pe care le faci um și acum avem r um care vine de la s și avem zero zero r unu unu și acum avem uh r, la rândul său, devine un gol șir și apoi șirul pe care l-am generat este zero zero unu unul care este în limbajul gramaticii și acum, uh, dacă te joci puțin cu asta, vei vedea că limbajul gramaticii sunt toate șirurile care arată ca șiruri de zerouri urmate de unități în regulă, așa că este clar, um, cred că vom avea un um, cred că următorul diapozitiv va avea un check-in și sperăm că asta ne va reuni pe toți pe aceeași pagină cu asta oricum um deci iată definiția noastră formală oricum avem o gramatică fără context este un patru-tuplu există patru părți de context pentru gramatică acestea sunt părțile despre care am discutat deja uh variabilele simbolurile terminale regulile um regulile sunt întotdeauna de forma unei variabile uh urmate de o săgeată la un șir de variabile și terminale, așa scriem, scrieți- o, deci aceasta este forma regulii și apoi avem variabila specială de început și Cu toții înglobăm asta într-un pachet, acest patru tuplu, asta este gramatica fără context, acum avem aici și acum poate un pic exagerat, dar hai să vorbim despre ce anume vorbind este modul în care gramatica procesează de fapt și produce șiruri. um, deci vom scrie notația standard pentru aceasta este că, dacă aveți două șiruri de variabile și terminale, așa că imaginați-vă că aveți un șir intermediar pe care l-ați generat în gramatică până acum, știți care ar putea fi 0 0 s 1 1 din linia anterioară, deci acesta este un șir intermediar care este până acum ceea ce ai generat, vei spune um, poate că ești tu și v ar putea fi următoarea linie de jos, deci asta înseamnă că vom scrieți u săgeata v și acea săgeată este cuvântul pe care îl vom folosi este yields vom spune u yields v um dacă poate merge de la u la v doar cu un singur pas de înlocuire um și apoi vom scrie u yields v într-un anumit număr de pași sau, de fapt, spunem că u derivă v dacă poate merge la u la v cu un anumit număr de substituții în loc de doar una și asta este folosit cu um săgeata de randament cu steaua deasupra ei pentru a însemna un anumit număr de um altul mod de a scrie, adică poți spune că mergi la v dacă există o grămadă de mișcări cu un singur pas pe care le poți face care te duc de la u la v și întreaga secvență se numește o derivație a lui v de la u, aceasta este o secvență de pași care treci prin a face aceste substituții una câte una pentru a te duce de la u la v conform regulilor gramaticale și, în sfârșit, dacă u este o variabilă de pornire, atunci numim acea secvență doar derivația lui v, ar putea fi derivația din variabila de început. dar asta se presupune că dacă nu spui că este o derivație din nimic, derivarea lui v în gramatică este derivarea lui v din variabila de început, este doar succesiunea de substituții pe care le faci un fel de știi ce ești ceea ce cred că v-ați aștepta acum, limba gramaticii este setul de șiruri de caractere pe care le puteți obține de la uh, începând cu variabila de pornire a gramaticii, bine și asta se numește un limbaj fără context, așa cum am menționat mai înainte deci este un context de limbaj liber, este limbajul gramaticii pentru ceva gramatică, bine, deci hai să ne verificăm aici din nou nimic prea greu, nimic de care să ne facem griji oricum, nu numărăm corectitudinea, deci, să vedem. Îți voi oferi două lucruri care arată ca niște gramatici, care dintre ele sunt de fapt gramatici și lasă-mă să trag acel sondaj, uh, bine, așa că care dintre acestea sunt gramatici valide aici sunt ambele, nici nu vreau să spun că poți să faci un fel de argument, fie știi oricum pentru amândoi, dar amândoi au un pic cam au o ciudățenie pentru ei, într-un fel, dacă tu, dacă le studiezi pentru o secundă, bine, asta e destul de convergent. împărtășește rezultatele um ok deci um deci de fapt răspunsul corect este b um [Muzică] și uh de ce este doar c2 în primul rând știi bine ce este în neregulă cu c1 c1 problema cu c1 este că regulile au lucruri în afară de o singură variabilă în partea stângă, deci a avea un b1 în partea stângă nu este legal într-o gramatică fără context, de fapt, există alte tipuri de gramatică, există un fel de gramatică numită gramatică sensibilă la context. Termenul fără context înseamnă că poți înlocui variabila independentă de contextul ei din șirul intermediar, atât de independentă de ceea ce este în jurul ei, dar aici se va înlocui această înlocuire, puteți înlocui b, dar depinde de existența uneia lângă ea, asta se numește un set de propoziții context de gramatică, dar nu este genul de caracter pe care îl vom folosi, care sunt doar gramatică fără context, așa că c1 este scos, nu este o gramatică legitimă fără context c2 lucrul care este puțin ciudat la c2 este dacă încercați să generați un șir în c2 veți vedea că nu există nicio modalitate de a scăpa de variabilele cu care veți rămâne întotdeauna blocat cu variabila acum, care nu încalcă definiția unei gramatici fără context, deci aceasta este o gramatică fără context, dar dar nu va putea genera șiruri de numai terminale, așa că aceasta este o gramatică fără context a cărei limbă se întâmplă să fie limba goală, dar asta este în regulă, așa că răspunsul corect aici este b că doar c2 aici este un context valid - gramatică liberă bine, obișnuită, să vedem întrebarea obișnuită: un șir u derivă în sine da un șir u derivă singur uh, asta este puțin o întrebare ezoterică pentru noi acum, dar da, un șir u în această definiție aici u stele săgeată sunteți legitim este ilegal, poate nu este conform modului în care am scris-o aici, dar este un lucru legal, oricum nu va conta cu adevărat pentru dvs., dar este ilegal, bine haideți să continuăm um să facem un alt exemplu oarecum interesant de gramatică fără context um aceasta este o gramatică care este um poate genera expresii aritmetice care implică plusuri și timpi, așa că aici este aici câte reguli sunt șase reguli aici fiecare linie reprezintă două reguli, deci e merge la e plus t sau t t merge la t ori f sau f și f merge la uh paranteza e paranteza sau a um acum, astfel încât variabilele vor fi simbolurile care apar în partea stângă et și f terminal simbolurile care vor fi simbolurile limbajului pe care o veți genera um vor fi plus simbolurile de timp, parantezele sunt doar simboluri terminale aici, așa că nu joacă niciun rol special în afară de asta și apoi aveți a care reprezintă un fel de operand um la care ar lucra acești operatori dacă ar exista de fapt o expresie pe care ați folosi-o, dar sunt doar simboluri din perspectiva gramaticii și, în sfârșit, variabila de pornire merge să fie așa cum apare în mod normal în partea din stânga sus a gramaticii în ceea ce privește modul în care o scrieți, așa că uneori ați putea specifica o variabilă de început diferită, dar altfel, dacă nu este specificată, este cea din acest colț, bine, așa că haideți doar vedeți uh câteva exemple de uh folosirea gramaticii pentru a genera uh un șir, așa că aici este un șir în limba un plus a ori a și și acest exemplu va dezvălui alte caracteristici interesante ale gramaticii, dar să vedem mai întâi în funcțiune Deci, din nou, voi încerca să vă scriu în ambele moduri în ceea ce privește arborele de analiză și șirul rezultat pe măsură ce faceți substituțiile, deci um the uh, așa că mai întâi începem cu e, apoi înlocuim e plus t și noi vezi șirul rezultat z plus t, dar acum, în timp ce facem substituții suplimentare, șirul rezultat pe care îl obțineți va evolua în consecință și sper să descopere că acest arbore de aici, imaginea din stânga vă arată structura diferitele substituții, în timp ce în dreapta vă arată doar șirurile pe care le obțineți ca urmare a acelor substituții [Muzică], așa că acum puteți genera acest șir special care este acum în limba acestei gramatici, puteți genera tot felul de alte șiruri de asemenea, așa cum știți, paranteza a plus o paranteză ori și așa mai departe și, de fapt, aceasta ar putea fi o bucată dintr-un limbaj de programare pe care încercați să o descrieți și o aplicație a gramaticilor fără context este de a descrie sintaxa limbajelor de programare știi care sunt programele legale cu care poți scrie în acel limbaj de programare și nu numai că gramatica poate fi folosită pentru a genera automat partea compilatorului uh pentru acel limbaj de programare care va interpreta um care ar uh interpretați structura intrării, cunoașteți așa-numitul parser care va da seama de semnificația intrării uh către compilator, astfel încât compilatorul să poată genera codul sau, dacă este un interpret, ar putea interpreta uh codul rezultat care l-ați dat, dar primul pas în ambele este să vă dați seama de semnificația, iar sensul este încorporat în structura arborelui de analiză acum, în cazul acestui arbore particular, doar pentru a vă da un sens. ce semnificație am în vedere acest arbore de analiză datorită structurii acestei gramatici are prioritate pentru ori peste plus, așa că în mod normal, atunci când notăm un plus de ori, presupui că vei face înmulțirea înainte de a face În plus, chiar dacă pare în al doilea rând, acesta este modul în care avem tendința de a scrie lucrurile și și această gramatică a grupat- o astfel pentru tine, grupează timpii mai jos în arbore decât plusul, astfel încât timpii vor fi făcute înainte de plus dacă vă imaginați că faceți acest lucru în ceea ce privește modul în care arborele vă ghidează, astfel încât arborele, după cum puteți vedea, are o anumită semnificație încorporată în el, acum nu vom folosi asta în acest curs, dar vreau doar să descrii asta ca o ilustrare a modului în care acest material poate fi aplicat acum, așa că știi că iată ce spun că arborele conține informații suplimentare acum, care sunt de asemenea relevante, dacă se întâmplă să ai o gramatică care ar putea permite mai mulți arbori de analizare. pentru același șir, bine, ceea ce se poate întâmpla, um această gramatică anume nu permite acest lucru, dar ați putea scrie alte gramatici care, după cum vom vedea într-un minut, ar putea genera același șir în mai multe moduri cu mai mulți arbori de analiză diferiți acum, ceea ce ar putea fi nedorit când aveți un limbaj de programare pentru că de obicei doriți să fie doar un singur sens pentru codul dvs., nu doriți să fie ambiguu și să aibă mai multe semnificații, dar ambiguitatea este că apare și nu este neapărat ceva ce suntem întotdeauna să vezi este un lucru rău, așa că știi, cred că, așa cum am menționat data trecută, o mare parte din acest subiect își are originea în lingvistică și de aici vine terminologia din gramatică și limbi și așa mai departe, terminologia subiectului chiar vine. din lingvistică, de fapt, unul dintre jucătorii cheie pentru aceasta este un membru emerit al facultății de la mit noam chomsky, el a jucat un rol esențial în a pune la punct o mulțime de aceste lucruri, dar um uh vă puteți gândi la gramatica ca fiind aplicabilă limbilor umane naturale ca Ei bine, așa că permiteți-mi să vă dau un mic exemplu ca o fereastră pop-up, aceasta nu este direct uh pop-up o înregistrare care nu este direct relevantă uh pentru materialul pe care tocmai l-am prezentat, ci doar un fel de curiozitate, um, dacă luați propoziția în engleză Băiatul a văzut fata cu oglinda, știi că există o singură interpretare naturală pentru acea propoziție sau există poate alte interpretări naturale pentru acea propoziție, așa că lasă-mă să-ți prezint asta ca un alt sondaj aici um și așa te întreb să te gândești la câte înțelesuri diferite ai putea găsi pentru uh, înțelesuri diferite rezonabile, adică poți să știi că dacă o să te dezlănțui, te poți gândi la miliarde de întâlniri, dar mă gândesc, în termeni de semnificații rezonabile, câte întâlniri ai putea ia pentru propoziție, uh, oamenii văd mai multe întâlniri decât văd eu, dar este în regulă, așa că este un rapid de ce nu mai dăm asta încă 10 secunde aici și apoi majoritatea dintre voi sunteți de acord cu mine. uh pot vedea aici că uh uh tu vezi că au fost două semnificații cele două semnificații pe care le văd aici pentru această propoziție sunt um când spui că băieții sau fata cu oglinda este cine are oglinda este băiatul care vede fata prin oglindă sau este fata care are oglinda și băiatul se întâmplă să o vadă așa că două sensuri foarte diferite pentru aceeași propoziție și asta e natura limbii engleze este doar uh așa cum um uh este este și este o structură ambiguă acolo și deseori rezolvăm acea ambiguitate în limba engleză cu alte informații pe care le-am putea avea, dar de obicei nu doriți să existe ambiguitate atunci când aveți o gramatică care descrie o programare ca limbajul de programare, bine, deci haideți continuă mai departe, um, așa că vorbind puțin mai mult despre ambiguitate, ți s-a promis un exemplu în care s-ar putea să ai o gramatică ambiguă um, deci dacă iei aceste două gramatici g2 și g3, g2 din ultimul diapozitiv și g3 este o gramatică similară în De fapt, gramatica are aceeași limbă um care vă oferă aceeași limbă, așa că l din g2 este egal cu l din g3 ambele descriu aceste expresii aritmetice um, dar în timp ce g2 are un arbore de analiză unic pentru fiecare șir pe care îl generați g3 poate avea mai mulți arbori de analiză pentru același șir, bine, așa că voi ilustra asta aici, deci aici este același șir pe care l-am generat data trecută de un plus de ori a în g3, arborele de analiză este de fapt și mai simplu aici, deci aici Vă arăt că sunt doar cele două înlocuiri pe care trebuie să le faceți începând de la e și apoi să obțineți șirul de un plus de ori a este a este a este o gramatică mai simplă într- un sens, dar voi există o altă analiză arbore care vă va da același rezultat și l-am scris mai jos aici cu susul în jos, așa că arborele de analiză superior grupează timpii înainte de plus sau mai mult în interiorul uh decât plus, dar arborele de analiza inferior nu face nu am acea precedență încorporată în ea și pot interpreta alternativ plusul ca având o prioritate mai mare decât ori și astfel, în acest sens, avem aici um o gramatică care este um are două interpretări pentru acest șir același și noi îl numim, hopa, numim asta o derivație ambiguă uh derivată ambiguu și gramatica în sine se numește o gramatică ambiguă um uh ok, așa că haideți să continuăm de la asta, apropo, există o întrebare aici care a apărut uh uh, de exemplu, un plus a este atât de ambiguu în g2 nu, dacă încercați să o aplicați, veți vedea modul în care g2 poate produce un plus a la un plus un plus a le va grupa pe primele două și apoi pe al doilea și apoi pe ultimul nu poți, nu poți deriva lucruri în mai multe moduri, vreau să spun că adăugarea este asociativă, dar gramatica nu este, nu gramatica pentru gramatică, va avea o ordine prescrisă pentru modul în care lucrurile sunt interpretate acolo, bine um deci asta e ambiguitate um deci haide să introducem automate push down um, care va fi omologul nostru automat pentru limbile fără context, în regulă, așa că voi introduce automatele push-down, un fel de trepte de schimbare aici și acum um este, mai întâi, oferind o nouă viziune asupra automatelor finite. Amintește-ți înainte, când am prezentat un automat finit, l-am dat în termeni de diagramă de stări pe care am arătat-o aici în formă miniatură pe imagine um uh am putea face asta pentru automate pushdown, dar imaginea tinde să fie foarte complicată, așa că voi lua o descriere de nivel mai înalt, um uh, pentru automatele pushdown, adică numesc o vedere schematică sau o diagramă schematică și acolo chiar nu mă duc să vă arăt stările individuale, dar vă voi arăta componentele individuale ale mașinii într- un fel mai mult abstract și dintr-o perspectivă mai abstractă și așadar din acea perspectivă um [Muzica] un automat finit are aici ceea ce voi numi controlul finit, așa că voi suprima detaliile stărilor din această imagine din această imagine. În cazul în care vor fi într-adevăr la fel din acest punct de vedere pictural, um, intrarea va apărea ca un șir care este scris pe ceea ce numim din nou bandă, aceasta este oarecum o terminologie anacronică în mine. zilele în care oamenii chiar și-au introdus intrările în computere pe o bandă, uneori, nu mai facem asta, dar acea terminologie s-a blocat și va fi o persistență um uh și mai târziu în curs, așa că ați putea la fel de bine să vă obișnuiți. deci intrarea va apărea pe o bandă sau, uneori, va fi numită o bandă de intrare și modul în care aparatul va citi de fapt acea intrare, uh, va avea un cap care va începe din partea stângă și se va mișca de la stânga la dreapta citind simbolurile de pe care apar pe banda de intrare unul câte unul, bine, deci aceasta este imaginea noastră a unui automat finit tocmai refăcut de data trecută, doar un mod diferit de a-l imagina acum, care va fi setarea Etapa pentru imaginea unui automat de împingere în jos, deoarece automatul de împingere este ca un automat finit, dar are o caracteristică suplimentară, are atașat un dispozitiv suplimentar și asta se numește stivă, bine, așa că iată o diagramă schematică pentru automatul de împingere în jos și asta este va fi o stivă care va fi practic o formă de stocare auxiliară. Acum amintiți-vă că o parte din limitarea pentru un automat finit a fost că aveam o cantitate limitată de memorie, așa că nu am putut face lucruri foarte simple, cum ar fi numărarea, deoarece am avut o memorie limitată, așa că automatul push-on va putea să-și folosească stiva ca un fel de memorie nelimitată, dar o memorie foarte restrânsă în modul în care poate fi utilizată, deci este nelimitată, dar încă restricționată, după cum vom vedea deci, modul în care automatul push down folosește această memorie suplimentară pe ceea ce numim stiva sau stiva push down este că poți scrie simboluri în loc să citești doar simboluri, dar acele simboluri pot fi citite doar la momentul scris sau citește chiar în partea de sus a acestei liste de simboluri și de fiecare dată când adaugi un nou simbol, celelalte simboluri care sunt deja acolo sunt împinse în jos, prin urmare, numele oamenilor se referă adesea la el ca un teanc de farfurii într-o cantină, dacă ai ați văzut vreodată acele lucruri sau vă puteți aminti de vremurile când mergeam la cantină, care se îndepărtează din ce în ce mai mult, dar dacă ai o cantină aveai o grămadă de farfurii și știi că ai scos farfuriile din ele. pe un izvor și au continuat să urce sau dacă adaugi mai multe, ar coborî și este aceeași idee, imaginează-ți că aceste simboluri de aici sunt cam pe un um pe un arc și cu cât le adaugi mai multe simboluri, cu atât coboară mai mult sau dacă le eliminați citind și citiți-le și eliminați-le, apoi se mută înapoi în sus, bine, așa că o împingere în afara tabatonului funcționează ca un finit ca un diametru finit nedeterminist, așa cum vom vedea că automatele împingere în jos vor fi întotdeauna pentru noi. să fie permis să fie nedeterminist, așa că nu vom studia împingerea asupra automatelor care sunt limitate să fie doar deterministe um uh voi spune mai multe despre asta într-o secundă, dar parcă funcționează ca un NFA, cu excepția faptului că pot scrie uh sau citesc simboluri din partea de sus a stivei și când scriu adaugă simbolul la împingerea în jos a stivei și când citesc elimină simboluri din stivă și astfel ridică stiva, bine le dăm speciale nume, așa că aceia dintre voi care au văzut deja stive, acesta este, știți că sunt sigur că o pălărie veche pentru voi, dar sunt sigur că acum toată lumea a văzut stive înainte, așa că numele special pentru scrierea pe o stivă se numește operație push astfel încât împingeți un simbol nou în partea de sus a stivei și împinge totul în jos, în timp ce atunci când citiți un simbol și îl scoateți din partea de sus a stivei, asta se numește pop, așa că citim și eliminăm noi întotdeauna Gândiți-vă la acestea ca mergând împreună scrisul și editarea și citirea și ștergerea sunt combinate, adică v-ați putea întreba de ce nu pot să- l citesc și să-l las în pace și să nu îl elimin, uh nu, puteți obține acest efect citind-l și apoi, uh, care îl îndepărtează și apoi îl pune înapoi dacă vrei cu adevărat să rămână acolo, dar modul în care îl setăm este că citirea vine cu eliminarea scrisului vine cu adăugarea de bine și se numesc împingere și popping bine, așa că hai să facem un exemplu, um, deci avem aici un automat de împingere în jos pentru o limbă pe care o vom numi d este un am văzut acea limbă înainte de a fi aceasta uh era um de fapt folosim aceeași literă uh pentru ea șirurile de zerouri urmate de unu unde numerele sunt aceleași dintre cele două, așa că zero la k unu la k nu am putea face asta cu un automat finit, vom putea face asta cu un automat push down și aici i uh um am crezut că am scris jos intrarea aici, dar bine, deci ideea de bază este că vă voi da o intrare acum și pushdown-ul tombitonului ar trebui să testeze dacă acea intrare este în limbă dacă este de această formă, acum are abilitatea de a folosi stiva pentru că știi că va trebui să numere câte zerouri are și așadar, modul în care o va face este să știi că am o grămadă de zerouri, sper, și apoi o grămadă de unele și vrei să vezi asta sunt de același număr, va lua zerourile și le va stoca pe stivă până când vede unul și apoi va începe să le citească pe cele și va elimina zerourile potrivindu-le unu la unu cu cele care sunt văzute în regulă, așa că inițial citiți zerourile și le împingeți pe stivă până când citiți unul și apoi le citiți pe cele uh în timp ce scoateți zerouri din stivă și intri în starea de acceptare dacă stiva este goală la fel ca cu un automat finit, cu excepția faptului că intrarea în starea de acceptare contează doar când ești la sfârșitul intrării, bine, deci fără să fiu nevoie să spun nimic, înseamnă într-adevăr că intri în starea de acceptare dacă stiva este goală la sfârșitul intrării șir, dar este un fel implicit, deoarece are efect doar la sfârșitul șirului de intrare dacă introduceți o stare de acceptare singur în mijloc undeva, nu contează, nu afectează nimic, um, bine, uh, vom face asta. luați o mică pauză și apoi ne vom întoarce în scurt timp să ne uităm la automatele împingeți din nou într- o definiție mai formală, um, lasă-mă să pun că vor dura cinci minute, așa că dacă pot să-mi dau seama cum să- mi iau cronometrul ecran aici sus da și vom uh camera când lumânarea se va arde până la nimic, ne vom întoarce și vom continua bine lumânarea noastră s-a ars și s-a stins, cred că nu m-am uitat niciodată să văd ce se va întâmpla la sfârșit. E bine să plec, hai să continuăm umh bine și lasă-mă să mă pun înapoi acolo, bine um [Muzică], așa că făceam împingere automate și tocmai am făcut acel exemplu de la zero la k1 la k acum că ai un stiva putem face tot felul de lucruri fanteziste pe care Fina Tamara nu le-ar putea face doar cu memoria lor limitată, bine, așa că haideți să aruncăm o privire la modul în care definim push down automata um [muzică] așa că acum uh push down automata va fi de fapt un șase tuple, deci avem niște chestii mai fanteziste aici, de care să se ocupe, nu prea multe, dar puțin um și uh, așa că are uh, hai să ne uităm la acestea puțin mai atent, deoarece există o noutate aici, avem doar alfabetul de intrare uh așa cum am avut înainte uh sigma, dar avem și gamma, care este alfabetul pentru uh folosirea stivei acum, vă puteți întreba de ce nu folosim același alfabet bine, este într-adevăr o chestiune de comoditate, am dori să putem să ai alte simboluri care ar putea include alfabetul de intrare, dar ar putea include și alte lucruri, așa că doar îți oferă mai multă flexibilitate în ceea ce privește ceea ce vei scrie pe stivă, bine, funcția de tranziție mai complicată, așa că cred nu știu dacă o să spun măcar care sunt celelalte lucruri, dar știi că acestea sunt stările de acceptare, aceasta este starea de pornire, așa că este la fel ca înainte, dar funcția de tranziție este un animal mult diferit aici în un automat push-down, deci să încercăm să despachetăm asta și să înțelegem ce spune, funcția de tranziție ne spune cum funcționează mașina cum trece de la o stare la alta, cum va citi intrarea, cum citește din stivă și ce anume s-ar putea să scrie și pe stivă pentru că totul se va întâmpla sub controlul programului, așa că ceea ce înseamnă asta aici este că știi când mașina este într-o anumită stare, citește un anumit simbol de intrare, hai să ignorăm șirul gol uh indicele pentru monument, așa că este într-o anumită stare citind un anumit simbol de intrare și cu un anumit simbol de stivă care apare în partea de sus a stivei, astfel încât acestea sunt toate informațiile care sunt disponibile pentru controlerul acestui automat pushdown, funcția de tranziție, starea curentă, următorul simbol de intrare și simbolul de la partea de sus a stivei și odată ce o avem, știm în ce stare nouă putem intra și ce simbol nou putem scrie în partea de sus a stivei, bine, așa că asta înseamnă partea dreaptă a specificației acestei funcții, deci asta este locul în care, uh, un fel de intrare în funcție, aceasta va fi ieșirea intrării de stare a funcției și un nou simbol care va apărea pe stivă, deci acesta este simbolul pop, acesta este simbolul de împingere, așa că acum există două lucruri care poartă explicație aici în primul rând, acesta este un set de puteri, așa că acesta va reprezenta, așa cum am făcut înainte, o mașină nedeterministă, putem avea mai multe posibilități și o vom reprezenta ca un set de posibilități pentru mașină la care ar putea merge în orice moment, voi da un exemplu despre modul în care un automat push down își folosește non-determinismul într-un minut, celălalt lucru este că acești epsiloni, așa că trebuie să înțelegem de ce sunt acolo și ne amintim că le-am avut pentru nfas-ul corespunzător când nfa a avut o tranziție epsilon, o tranziție goală, astfel încât să poată merge de-a lungul acelei tranziții fără a citi nicio intrare, așa că aceasta va juca același rol aici, așa că dacă aveți um în loc de un simbol de intrare din sigma care apare în aceasta um uh parte a pe care o știi uh pentru funcția de tranziție, în schimb, ai un epsilon care apare, ceea ce înseamnă că tranziția că acea mișcare a mașinii se poate întâmpla fără a citi niciun simbol de intrare la fel ca pentru nfa sau dacă să apară un epsilon pentru simbolul stivei, ceea ce înseamnă că poți face acea tranziție fără a citi niciun simbol stivă, astfel încât orice se află în partea de sus a stivei, nu contează, mașina poate face acea mișcare și nici nu va citi nimic. Nu o să scoată nimic, doar că va continua fără să se uite deloc la stiva sau s-ar putea să le aibă pe amândouă, caz în care va trece de la o stare la alta fără să se uite la intrare sau în partea de sus stiva deci asta înseamnă posibilitatea de epsilon pentru um pentru funcția de tranziție în acele locuri, epsilonul care apare aici înseamnă ceva puțin diferit, dar foarte asemănător ceea ce înseamnă că um [muzică] nu vom scrie orice din partea de sus a stivei care va fi, vom merge într-o stare nouă, dar fără să scriem, așa că vom lăsa stiva în pace, um, aici înseamnă că nu vom citi nimic dacă se află în această poziție în această poziție. Poziția înseamnă că nu vom scrie nimic în regulă, așa că toate aceste lucruri sunt valide și legale din punctul de vedere al construirii unui automat push-down și am cam ilustrat aici, știi doar cu un mic exemplu. dacă aveți delta care se aplică unei stări q citind un simbol de intrare a și scoateți un c din partea de sus a stivei, atunci s-ar putea să fiți să spunem în acest caz două posibilități la care ați putea ajunge, s-ar putea ajunge la stările r1 sau la stările r2 și în primul caz veți ajunge să scrieți un d împingând un d pe acest vârf al stivei și în cel de-al doilea caz ați împinge un e în partea de sus a stivei, bine, deci asta încerc să fac. te ajută să te uiți la această notație, poți ști că știi, sper că acest lucru este clar pentru tine, eu sunt sigur că pentru unii dintre voi este prea lent, dar pentru alții încerc să vă ajut, dar dacă vă lupți cu adevărat această notație în acest moment știi că trebuie să te uiți și să te asiguri că o urmezi, pentru că va deveni mai greu de acolo, o să încetez să mai trec peste aceste tipuri de puncte și dacă Încă te chinui, nu o poți obține, aceasta nu este clasa potrivită pentru tine, o să fiu sincer, pentru că o să decolăm așa cum știi că vom începe să accelerăm destul de repede, bine deci este o mașină nedeterministă, um, acceptăm um, așa cum am făcut-o înainte, s- ar putea să existe mai multe fire diferite ale calculului pe care veți ajunge să le acceptați dacă unele dintre fire sau ceea ce cel puțin unul dintre fire se termină. într-o stare de acceptare la sfârșitul șirului de intrare, bine atunci când automat acceptăm în general, este doar modul în care ne gândim în mod normal la non-determinism, puteți folosi din nou modelele pe care le aveam înainte în ceea ce privește ghicitul sau paralelismul, orice funcționează pentru dvs. și, uneori, lucruri diferite funcționează în diferite ocazii diferite, uh, dar așa funcționează non-determinismul, vom face un exemplu acum, bine, aici este o împingere asupra automatului pentru un alt limbaj pe care nu l-am văzut până acum, nu cred că poate că am um, care își va folosi non-determinismul într-un mod esențial, acesta este un limbaj care va ajunge acolo unde non-determinismul va fi critic, um, fără el, nu poți împinge deterministă asupra automatului, care este ceva apropo, oamenii studiază și există o secțiune a cărții mele despre acea secțiune 2.4, deoarece are relevanță pentru aplicații, nu o vom aborda în acest curs, așa că puteți sări peste secțiunea 2.4, este destul de tehnic, uh, voi avea să spun um, dar totuși destul de interesant și frumos dacă îți plac lucrurile astea, dar este tehnic, nu o vom face um, așa că iată um acest șir de intrare w w invers pentru toate w posibile peste alfabetul nostru zero unu și ce w invers apropo, înseamnă că scrie w înapoi uh, deci acestea sunt toate șirurile urmate de o inversare a aceluiași șir, bine șirul scris înapoi, um, într-adevăr, te poți gândi la acestea ca uh știi, deci acestea sunt șiruri care um, bine, aici este un exemplu de genul 0 1 1 1 1 0 șirul scris înapoi, deci acesta este un șir în limba care apare pe o bandă așa cum am descris-o bine, deci cum va recunoaște mașina această limbă, este destul de asemănătoare oarecum cu cea de dinainte, dar cu o diferență importantă și dacă vă imaginați, mă gândesc din nou, îmi place să folosesc acest tip de și să antropomorfizez aceste lucruri, punându- vă în locul mașinii și gândindu-vă cum ați face asta, așa că dacă vă imaginați să obțineți aceste simboluri unul câte unul zero unu unul pe care nu știi ce urmează, pe măsură ce primești simbolurile, trebuie să-ți dai seama cum să potriviți a doua repriză cu prima repriză, așa că veți pune prima jumătate pe stivă și apoi veți face scoateți prima jumătate și potriviți-o cu cu a doua jumătate, în mod convenabil, prima jumătate iese înapoi, stiva este primul în ultimul ieșit, așa că iese în ordine inversă, așa că este perfect pentru a se potrivi cu a doua jumătate, dar partea dificilă cu acest limbaj este cum știi când ești la mijloc, pentru că nu poți să vezi, restul, poți să vezi doar ceea ce ai văzut până acum nu știi ce urmează, așa că știi că, uh, când citești al doilea, în acest moment, citești zero, unul acum, citești al doilea, nu știi că poate că va fi un zero următor asta și va fi totul, așa că poate ar trebui să te decizi că acest punct aici pe care l-am marcat um uh este punctul de mijloc și ai pus zero unul pe bandă și apoi începi să-l apari pe al doilea și al doilea și să-l potriviți lasă-te cu primul, um, asta ar fi un lucru tentant de făcut, dar pur și simplu nu știi um și acolo va fi esențial non-determinismul, așa că lasă-mă să scriu mai multe despre asta, așa că ceea ce faci. O să faci este să citești și să împingi simboluri de intrare, dar fără să ghicești în mod determinist că te afli la mijloc, așa că acum vei repeta asta în mod determinist și vei continua să citești și să împingi simbolurile pe stivă sau tu o să mergi la doi, hotărând asta sau ghicind că te afli la mijloc și acum este timpul să începi să citești și să popping în loc să citești și să împingi, așa că vei citi simbolurile de intrare și vei apărea simbolurile stivei comparând două simbolurile pe care le citiți cu partea de sus simbolurile pe care le eliminați din stivă, dacă vreodată nu sunt de acord, atunci acest fir de non-determinism respinge deoarece fie intrarea nu este în limbaj, fie cel puțin ați făcut-o dvs. o alegere greșită în ceea ce privește locul în care este punctul de mijloc și apoi veți intra în starea de acceptare dacă stiva este goală și veți ignora această parte pentru momentul referinței la software, hai să vorbim despre asta într-o secundă dar vreau doar să mă asigur că înțelegem că, la un nivel intuitiv, modul în care această mașină își folosește non-determinismul pentru a recunoaște acest limbaj, deoarece non-determinismul este esențial și este important să îl înțelegeți, așa că permiteți-mă să fac niște comentarii secundare și apoi vom reveni la această remarcă software, așa că în primul rând o întrebare care apare foarte bine, nu acordați atenție chat-ului de aici, îmi pare rău, așa că dacă nu primiți răspuns de la mine, încercați tas, dar unul Una dintre întrebările care apare mult atunci când se gândesc la non-determinism pentru automatele push down este ce se întâmplă cu stiva, stiva este replicată în non-determinism de fiecare dată când mașina se bifurcă la fel ca orice altceva este replicat, astfel încât un întreg de fiecare dată când există o bifurcătură în non-determinism și mașina se ramifică în posibilități multiple, întreaga mașină reproduce starea curentă poziția curentă a capului, care este stiva și conținutul său, toate acestea sunt replicate um și două părți ale celor două ramuri sau cele două părți ale furculiței, fiecare continuă independent în felul lor vesel, bine făcându-și treaba independent și apoi, dacă vreunul dintre ei acceptă, acesta este singurul mod în care există un fel de comunicare pentru că cel care acceptă ridică steagul și apoi mașina generală este setată să accepte în regulă, așa că furcile non-deterministe reproduce teancul de a spune asta vreau doar să mă asigur că ai asta și atunci acest limbaj necesită non-determinism asta am spus mai devreme um, așa că modelul nostru de timp de împingere pda va fi nedeterminist, adică ați putea avea exemple care sunt deterministe, dar modelul va permite întotdeauna non-determinismul, bine ce este asta despre software, așa că dacă uitați-vă la această definiție formală aici, nu are nicăieri în ea capacitatea de a testa dacă stiva este goală, ceea ce nu face parte din specificația hardware, cel puțin așa cum o descriem pentru un automat push-down, vă puteți imagina pe altcineva descrie împingerea pe tama într-un alt mod, care dă asta ca o primitivă, dar nu vom face asta de ce, deoarece nu avem nevoie de o primitivă pentru asta, puteți obține efectul de a testa dacă există o stivă goală chiar dacă nu ai asta ca o primitivă pentru mașină, pentru că ceea ce ai putea face este să pornești mașina atunci când chiar de la primul lucru pe care îl face este că scrie un simbol special pentru a marca partea de jos, știi ce se va întâmpla. în cele din urmă, în partea de jos a stivei, va exista un simbol special, poate un simbol cu ​​semnul dolarului, acesta este primul lucru pe care îl face mașina și apoi procedează ca înainte, dacă vede din nou acel simbol semnul dolarului, știe că teancul este efectiv gol, bine astfel încât să puteți obține efectul testării pentru ca stiva să fie goală, chiar dacă nu aveți o primitivă pentru asta și nu ne vom agita de fapt cu unele detalii de acest fel, așa că le puteți folosi atunci când vă scrieți temele. setează că poți folosi doar presupunerea că poți testa stiva goală, ceea ce o să fac eu însumi, bine, deci hai să continuăm bine, așa că da, așa că acum vom face ceea ce vom face. demonstrează-l pe cel al nostru până acum, chiar nu am dovedit nimic, tocmai am dat niște definiții și câteva exemple pe care le-ar fi făcut astăzi, vom ajunge la teorema noastră mare, care de fapt este importantă și are ceva carne în ea și așa facem conversia, știi, susțin că pentru a pune gramaticile fără context și automatele push down sunt echivalente, vom demonstra că echivalența într-o direcție transformând gramaticile în automate push down, bine, așa că lasă-mă să-ți arăt cum asta merge într-un fel, um, este o dovadă frumoasă, nu foarte complicată, dar are puțină carne, uh, așa că dacă vă dau o gramatică aici, ceea ce vă voi spune cum să faceți este să convertesc acea gramatică într-un automat push down, care nu aceeași limbă bine, așa că dacă sunteți verificat pentru un minut, vă rugăm să reveniți pentru că începem acest subiect acum că vă puteți gândi puțin la acest punct de reintrare bun, uh, dacă ați cam fost fac altceva despre care nu pot spune lucru bun, așa că în regulă, transformând o anumită gramatică într-un automat push down, cum va funcționa asta, deci ideea este în regulă înainte să vă spun ideea, să ne gândim din nou împreună. Îmi place să mă gândesc la automatul care împinge în jos construirea unui automat automat așa cum ai face-o, așa că o gramatică este un dispozitiv de generare care generează șiruri un automat împingere în jos sau să mă gândesc la asta ca tu ești un recunoaștere ți se oferă un intrare și vrei să știi dacă este în limbă, așa că vrei să știi este posibil ca acea gramatică să genereze acea intrare care ți-a fost dată, deci cum mergi cum mergi cum vei face asta um și uh te duci cum ai de gând să testezi dacă intrarea este în limba gramaticale bine, lucrul pe care l-ai face în mod natural este să spui bine, pot deduce acel șir folosind regulile gramaticale, permiteți-mi să încep cu șirul de început și încercați să faceți înlocuiri și să vedeți dacă primesc șirul care mi se dă și dacă îl pot obține, atunci știu că este în limba corectă, este un lucru firesc, veți încerca să încercați să faceți, așa că știți că încercați. să faci înlocuirile chiar și să ajungi la șir acum, lucrul este că sunt multe, ar putea exista multe înlocuiri diferite pe care le-ai putea face și știi că pare un lucru cu adevărat provocator, uh, greu de a-ți da seama ce înlocuiri să folosești dintre numeroasele posibilități care există unde va interveni non-determinismul pentru că te poți gândi la tine că ghicești ce substituții să faci și vei face întotdeauna o ghicire corectă, astfel încât alegerea ce substituții să faci nu va fi o problemă pentru tine. va fi gestionat de non-determinist, așa că imaginați-vă că veți face întotdeauna înlocuirea corectă, dar acum provocarea este cum țineți evidența rezultatelor intermediare în timp ce faceți acele înlocuiri și acolo se duce stiva să vină în mașină va nota acele rezultate intermediare pe stivă, dar chiar și acolo există o subtilitate care este o subtilitate importantă la care trebuie să te uiți, așa că hai să încercăm să le unim până acum înainte de a ajunge la acea subtilitate, bine, așa că Am menționat că automatul push down va începe cu variabila de pornire și va ghici că va ghici înlocuirile pentru a face că va menține rezultatele intermediare pe stivă când se va termina cu toate înlocuirile și are numai șirurile terminale de pe stivă se poate compara cu intrarea și să vadă dacă a primit ceea ce trebuie, deci dacă a făcut toate presupunerile corecte, așa că te gândești la asta ca la o ghicire care face ghicirile corecte, dar în cele din urmă trebuie să verifici pentru a face sigur că ai dreptul, că ai făcut tot ceea ce trebuie și accepti când, atunci când lucrurile s- au potrivit, te cunoști și ai făcut toate presupunerile corecte, așa că trebuie să verifici dacă în cele din urmă. de fapt, am primit acea informație de la efectuarea acestor înlocuiri, deci hai să încercăm să vedem acest lucru funcționând în acțiune și apoi vei vedea subtilitatea, delicatețea, o problemă care va apărea, sperăm că o urmărești cel puțin în parte ceea ce spun până acum, bine, deci aici este intrarea, știm că aceasta este o intrare în limba în care am văzut acest exemplu de mai multe ori, așa că iată intrarea care apare pe banda de intrare a plus un de ori și acum, împingerea automatului ar trebui să accepte acea intrare, deoarece este în limba terenului, bine, așa că va funcționa scriind mai întâi pentru a începe variabila de pornire pe stivă și apoi făcând substituțiile pe măsură ce mergem. de-a lungul bine, deci vom înlocui noi noi uh e merge la e plus t deci facem prima înlocuire și apoi facem următoarea înlocuire aici e așa că eu sunt eu dacă te uiți la acest arbore aici, ceea ce înseamnă că acesta este arborele potrivit pentru acel uh pentru acea intrare, așa că înlocuim e cu t uh până acum atât de bine că automatul poate face acea înlocuire, apoi următoarea înlocuire va fi puțin uh, așa că noi" re unde e plus t am înlocuit aici avem t plus t și acum vom înlocui de t ori f care este acest t aici vrem să înlocuim asta și care apare ca de t ori f acum pe stiva acum dacă mă urmărești, ar trebui să devii brusc nervos pentru că tocmai am înșelat, e în regulă, um facem înlocuiri, făcând aceste înlocuiri chiar în partea de sus a stivei, deoarece automatul de împingere în jos are acces la partea de sus, așa funcționează stivele, dar nu are acces în adâncul stivei, care nu este stilul de casă, nu așa funcționează stivele, deci este o înșelăciune, dar ignorând înșelăciunea pentru un minut, dacă le-ai putea înlocui pe acelea, um face acele înlocuiri în adâncul stivei, toate acestea ar funcționa, am fi bine ai face înlocuirile, una după alta, până când nu ai rămas fără variabile și apoi ai șirul aici și îl vei compara și îl vei compara cu intrarea, totul este făcut în mod corect, astfel încât lucrurile sunt în ordinea corectă, astfel încât să știți că după toate înlocuirile ați avea un plus de ori o ședință aici pe stiva cu care vă potriviți, comparați asta cu intrarea se va potrivi și veți ajunge să acceptați totul bine deci cum ne ocupăm de această problemă aici, accesul problemei de sub stiva de trepte, partea de sus a stivei este înșelăciune ce vom face în schimb, așa că ideea este de fapt destul de simplă, dacă ați înțeles ce am spus până acum. Știu că remedierea asta nu este de fapt prea rău, uh uh, un fel de dispariție aici uh pune mai multă lumină asupra imaginii mele, așa că cum facem asta, uh, cum obținem efectul accesului de sub partea de sus a stivei și modul în care vom face asta este făcând obs ceea ce vom face, vom face doar înlocuiri pe care le putem face în partea de sus a stivei, astfel încât oricând există o variabilă în partea de sus a stivei. stiva vom face înlocuirea pentru că suntem cei de sus la care putem accesa acum. Ce se întâmplă dacă avem un simbol terminal în partea de sus care ne blochează accesul la variabilele variabile de mai jos, de fapt, acesta este un caz ușor de gestionat, deoarece avem simboluri terminale stând în partea de sus, oricum nu se vor schimba niciodată, așa că ați putea la fel de bine să le potriviți cu intrarea în acel moment, așa că atunci când aveți un terminal așezat în partea de sus, vom citi doar un alt simbol de intrare și vom face acest lucru și îl vom potrivi. acolo și continuăm să citim simbolurile terminalului până când avem o variabilă așezată în partea de sus, apoi facem o înlocuire și continuăm să înlocuim variabile până când avem un terminal, apoi o citim, apoi o comparăm cu intrarea și, făcând acest lucru um, vom ajunge să obținem același efect pe care l-am descris înainte, fără a fi nevoie să săpăm vreodată în interiorul stivei și să facem înlocuiri acolo, toate se vor ridica în vârf și le putem face oricând la partea de sus bine, așa că oricum, uh, știi, am uitat să fac asta aici, așa că în schimb, înlocuiește variabilele numai când sunt în partea de sus a stivei, dacă un terminal este în partea de sus, compară-l cu intrarea și respinge dacă acestea" nu sunt egal, așa că dacă aveți vreodată ceva care nu se potrivește cu modul în care ar trebui să facă asta, vreau să spun că acel fir pur și simplu va eșua, știți că atunci nu a fost o alegere rea, uh, a fost făcută o alegere nedeterministă sau poate că intrarea nu a fost în limba oricum și nu există alegeri bune, așa că aici animația mea s-a rupt aici, așa că lasă-mă să pun totul în fața ta, așa că iată construcția reală. Apăsați simbolul de pornire pe stivă dacă partea de sus a stivei uh este o variabilă înlocuiți-o cu o parte dreaptă corespunzătoare care face o alegere nedeterministă dintre diferitele posibilități, dacă este un terminal, îl deschideți și îl potriviți cu următorul simbol de intrare și dacă stiva este goală, acceptați, așa că iată cum stiva ar căuta de fapt această intrare specială, știți că ar începe la fel ca și ați avea e și apoi ați înlocui cu e plus t și apoi vom înlocui întotdeauna facem substituțiile din partea de sus, astfel încât e să fie înlocuit cu f da, nu, acest diapozitiv am încurcat. Îmi cer scuze, așa că este înlocuit cu t care este înlocuit cu f um și ideea este că atunci când ajungi la o ședință în partea de sus, iartă greșelile de scriere aici, acum avem un simbol terminal și acesta va fi corelat cu următorul simbol de intrare și va fi eliminat și acum avem doar plusul și t rămase și apoi plusul este, de asemenea, un simbol terminal care va fi potrivit cu următorul lucru pe care avem doar un t. în partea de sus și acum putem face o înlocuire, bine, așa că așa funcționează, bine, asta e tot ce am vrut să spun, cred că um oh, a fost una doar remarcată, așa că asta nu este, nu vom demonstra asta, dar cred că este uh Trebuie să spun asta că, de fapt, puteți face conversia și în cealaltă direcție, puteți converti un um, deci a este un limbaj fără context dacă și numai dacă un automat push-down recunoaște a și um dacă nu ați văzut dacă și numai dacă este o expresie pe care o voi folosi uh uh din nou și din nou, așa că ar trebui să vă obișnuiți, înseamnă dacă și numai dacă și ceea ce înseamnă doar că implicația merge în ambele sensuri, deci a este un context uh - limbajul liber fără context implică faptul că unii împinge timpul în timp recunoaște a și invers, așa că sunt cu adevărat două lucruri pe care trebuie să le demonstrezi ori de câte ori ai un dacă și numai dacă trebuie să dovedești ambele direcții, așa că te gândești la despărțirea în acest fel le-am pe jumătate direcția înainte, am dovedit deja, transformând un context push uh gramatică liberă într-o împingere în jos a automatului în direcția inversă, nu vom demonstra că este în carte dacă ești curios și ești responsabil știind că adevărul este adevărat, dar nu trebuie să știi dovada, care este o compătură oarecum complicată și știi că cred că ne-ar lua prea mult timp să o parcurgem, așa că nu ești responsabil pentru asta. deci există o ultimă verificare aici pe care o am pentru tine, care este doar o întrebare la care poți răspunde pe baza materialului pe care l-am prezentat până acum este fiecare limbă obișnuită și o limbă fără context doar da nu sau nu ești sigur, deci lasă-mă să lansez asta ca sondaj aici, bine pe cale să se închidă, um [Muzică] terminând sondajul și partajarea rezultatelor asta. Cred că aproape că, uh, majoritatea dintre voi ați avut unii dintre voi uh nu sunteți siguri că fiecare limbă este de fapt o limbaj fără context și modul de a vedea asta este că fiecare limbă obișnuită poate fi făcută de un dfa sau un nfa, așa cum am arătat deja și um dfa sau un nfa este de fapt doar un automat push-on care nu își folosește niciodată stiva, astfel încât se poate gândi întotdeauna la un DFA ca la un automat push down și am susținut deja că automatele pushdown sunt echivalente cu gramaticile fără context și, prin urmare, fac limbajele fără context, astfel încât orice puteți face cu un DFA îl puteți face și cu un push. -down automaton și, prin urmare, toate limbile obișnuite sunt, de asemenea, limbi fără context, bine, așa că, cu asta, hai să punem lucrurile împreună, o scurtă recapitulare despre ceea ce am făcut până acum în clasa în care am Avem limbajele obișnuite și limbajele fără context pe care le-am avut cele două forme de a ajunge la ele forma de recunoaștere, care este ca perspectiva bazată pe automate, fie un dfa, fie un nfa, în cazul limbilor obișnuite, împinge automat automat pentru limbi fără context și pentru generatori am avut expresia regulată uh pentru limbile obișnuite și gramaticile fără context pentru limbile contextuale ok și așa cum tocmai am subliniat cel mai mult în ultima noastră verificare, limbile obișnuite formează un subset și, de fapt, un subset adecvat al limbilor fără context, așa cum se arată în această diagramă Venn, deoarece am expus deja limbi fără context, dar care nu sunt obișnuite, așa că o revizuire rapidă am definit gramaticile fără context. și limbile asociate acestora limbile fără context definim automate push-down și am arătat cum să convertim gramaticile fără context în push-down automat um și asta este tot ce am pentru tine astăzi, bine, iată o întrebare la care voi răspunde tuturor de ce facem ne strict la o stivă de ce nu folosim memoria cu acces aleatoriu, vom folosi memoria cu acces aleatoriu, um, pentru următorul model numit mașină de turing și vom introduce asta, cred că lângă următoarea prelegere, așa că acesta va fi model cu care ne vom menține pe tot parcursul mandatului, dar nu am folosit introducerea unor modele mai slabe, uh, ca un fel de preludiu la un scop mai general, uh model de calcul, uh, pentru a ne încălzi și de asemenea, pentru că pentru modelele mai slabe le puteți analiza complet într-un mod în care nu puteți returna mașini pe care le veți putea, după cum veți vedea, puteți determina proprietățile limbajelor pentru modelele mai slabe pe care nu le puteți returna pentru modelele mai generale. și deci cred că este util să aveți acea perspectivă despre care știți că pentru unele cazuri puteți obține o analiză completă și pentru alte cazuri nu puteți, um, dar oricum um, acesta este motivul pentru care suntem restricționați mai strict la stivă, pe lângă faptul că acestea modelele au aplicații care cred că merită să vedeți de ce da, un motiv pentru care am ales o stivă bine de ce am ales o stivă și nu o altă structură de date pentru temporarul nostru, pentru stocarea noastră suplimentară și motivul pentru o stivă pentru un lucru în stiva este exact ceea ce aveți nevoie pentru a ajunge la corespondența cu gramatici fără context, um, dacă utilizați un alt spațiu de stocare, cum ar fi coada, de exemplu, în loc de stivă, de fapt, obțineți un rezultat foarte diferit și este de fapt un lucru interesant. exercițiu pentru a vedea ce se întâmplă ce obțineți dacă utilizați o coadă ca stocare externă în loc de ca stivă, uh, este o problemă bună cu temele, poate o voi atribui um uh hai să vedem um nfa bine uh am arătat așa că am arătat am arătat că non-determinismul poate fi eliminat pentru automatele finite, așa că nfas și dfas sunt echivalente, ce zici pentru automatele pushdown, răspunsul este nu, nu sunt echivalente, cred că am menționat asta mai devreme, dar nu mă deranjează să o repet, există anumite limbaje care pot fi făcute numai cu automate nedeterministe push down și nu pot fi făcute cu automate deterministe push down, de exemplu acel limbaj w w invers care necesită non-determinism pentru ca mașina să poată ghici unde este mijlocul așa um Bine, o să plec, mulțumesc, ne vedem marți