[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bine, oameni buni. Suntem aici din nou. Bine ați revenit pentru un alt episod din teoria calculului. Aceasta este cursul numărul 3. Voi trece în revistă ceea ce am făcut. Ne-am uitat la automate finite și la limbaje obișnuite. Acestea sunt limbile pe care automatele finite le pot recunoaște. Și am vorbit despre nondeterminism. Deci am avut automate finite nedeterministe și automate finite deterministe. Am arătat că sunt echivalente. Ne-am uitat la proprietățile de închidere peste uniunea, concatenarea și steaua operațiilor obișnuite și am arătat că limbajul obișnuit este într-adevăr-- clasa limbajelor obișnuite este închisă sub acele operații obișnuite. Și am folosit construcțiile pe care le-am dezvoltat în demonstrarea acelor proprietăți de închidere pentru a arăta că... putem oferi o modalitate de a converti expresiile regulate în automate finite. Așadar, a fost parțial către obiectivul nostru de a arăta că aceste expresii regulate și automate finite sunt echivalente în ceea ce privește clasa de limbaje pe care o descriu, și anume, limbajele regulate. Deci, expresiile regulate ale automatelor finite sunt interschimbabile din perspectiva tipurilor de limbaje pe care le puteți face cu ele. Așa că vom termina asta astăzi. Deci, să aruncăm o privire la următoarele subiecte pe care le vom acoperi. Vom inversa construcția pe care am dat-o data trecută, ceea ce ne-a permis să transformăm expresiile regulate în automate finite. Acum vom merge înapoi. Vom arăta cum să convertim automatele finite înapoi în expresii regulate. Și că-- acele două construcții împreună ne arată că expresiile regulate și automatele finite pot fi interconvertite unele de altele și, prin urmare, sunt echivalente în ceea ce privește tipurile de lucruri pe care le pot face în recunoașterea sau generarea limbajului. Apoi, vom demonstra că... vom vedea cum demonstrezi că anumite limbi nu sunt obișnuite, depășesc capacitățile automatelor finite. Și, în sfârșit, la sfârșit, vom introduce un nou model de calcul care este mai puternic decât automatele finite și expresiile regulate, și anume, gramaticile fără context. Aceștia pot face alte tipuri de limbaje pe care modelele mai simple de expresii regulate cu automate finite nu le pot face. Și aș dori, de asemenea, să remarc că o mare parte din ceea ce facem este o pregătire pentru modelele mai puternice de calcul pe care le vom analiza mai târziu... ei bine, într-o săptămână sau cam așa... care sunt calcule cu scop mai general. Dar, pe parcurs, introducerea acestor modele de automate finite în limbaje fără context este interesantă și utilă, deoarece multe dintre acestea -- un număr -- acele modele se dovedesc a fi utile într-o serie de aplicații, fie că este vorba de lingvistică la limbaje de programare. . Și o varietate de părți diferite ale informaticii și din alte domenii folosesc și aceste noțiuni. Deci sunt noțiuni utile dincolo de acest curs. Așa că vreau doar să... câteva lucruri administrative pe care să le abordez. Vom avea check-in-uri suplimentare astăzi, așa cum v-am menționat. Vom începe să numărăm participarea -- nu corectitudinea, doar participarea -- la check-in-urile live. Deci, cu asta, să trecem la materialul de astăzi. După cum am menționat, vom arăta cum să convertim automatele finite în expresii regulate. Și asta va completa echivalența noastră de automate finite și expresii regulate. Așa că, pentru a recapitula ceea ce am făcut ultima dată, am arătat că, dacă aveți o expresie regulată și descrie un anumit limbaj, atunci acel limbaj este obișnuit. Deci, cu alte cuvinte, avem o modalitate de-- am oferit o modalitate de a converti expresiile regulate în automate finite, așa cum se arată în această diagramă. Asta am făcut ultima dată. Acum vom merge pe cealaltă direcție. Vă vom arăta cum să convertiți-- oh, și doar un reamintire în cazul în care vă puneți memoria în funcțiune, poate vă va ajuta să vă amintiți că noi am făcut de fapt un exemplu al acelei conversii . Ne- am uitat la această expresie regulată, o uniune ab star. Și de fapt am lucrat prin procesul de conversie. Hopa! Trebuie să mă fac mai mic, ca să poți vedea toate astea. Am trecut prin procesul de conversie a unei stele uniune ab ca un exemplu al faptului că... de... a făcut o greșeală... [RÂDE] OK. Ei bine, am trecut prin procesul de a face efectiv acea conversie. Și acum vom arăta cum să procedăm invers. Așa că vom inversa asta și vom merge înapoi în altă direcție. Deci, teorema de astăzi este să arate că, dacă a este regulat, și anume, este limbajul unui automat finit, atunci îl poți converti într-o expresie regulată care va descrie același limbaj. Deci, practic, vom oferi o conversie de la automate finite la expresii regulate. Dar înainte de a face asta, va trebui să introducem un nou concept. Așa că nu ne vom putea scufunda direct în acea conversie. Va trebui să facem... mai întâi să introducem un nou model, care va facilita acea conversie. Și acel nou model se numește -- este încă un alt tip de automat finit numit automat generalizat nedeterminist finit , sau un NFA generalizat, sau pur și simplu un GNFA. Deci aceasta este o altă variantă a modelului de automat finit. Și din punct de vedere conceptual, este foarte simplu. Este similar cu NFA-urile. Îți voi da... iată o fotografie a unui GNFA numit G, G1. Foarte asemănător cu NFA-urile. Dar dacă te uiți la asta pentru o secundă, vei vedea că tranzițiile au etichete mai complicate. Pentru NFA, permitem doar simboluri unice, sau șirul gol, să apară pe etichete. Acum, de fapt, vă permit să puneți expresii regulate complete pe etichetele automatului. Acum, trebuie să înțelegem cum își procesează un GNFA intrarea. Și modul în care funcționează nu este complicat de înțeles. Când primiți o alimentare șir de intrare - când un GNFA procesează un șir de intrare, acesta începe la starea de pornire, așa cum v-ați imagina. Dar acum, pentru a merge de-a lungul unei tranziții, în loc să citești doar un singur simbol sau șirul gol, ca în cazul mașinii nedeterministe, de fapt ajunge să citească un șir întreg la un singur pas, cam la o singură mușcătură. Poate citi un șir întreg și poate merge de-a lungul acelei săgeți de tranziție, cu condiția ca porțiunea de intrare pe care a citit-o să fie în expresia regulată pe care acea tranziție o are ca etichetă. Deci, de exemplu, aceasta-- puteți trece de la q1 la q2 într-un singur pas în acest GNFA citind a, a, b, b de pe intrare. Deci citește toate acele patru simboluri dintr-o dată. Pur și simplu le ridică și apoi se mută de la q1 la q2 într-un singur pas. Și apoi, când este în q2, poate citi aab și trece la q3. Și se întâmplă q3, nu există încotro. Deci aceasta va fi o mașină nedeterministă. Pot exista mai multe moduri diferite de procesare a intrării. Și dacă oricare dintre ei ajunge într-o stare de acceptare la sfârșitul introducerii, spunem că GNFA acceptă. Deci, este similar cu nondeterminist-- cu NFA în modul în care funcționează criteriul de acceptare. Deci ai putea sa faci un exemplu. Dar sperăm că conceptul de modul în care funcționează acest lucru este rezonabil - îl puteți cumpăra cel puțin , că procesează intrarea în bucăți la un moment dat. Și acele bucăți trebuie descrise prin expresiile regulate de pe săgețile de tranziție, pe măsură ce se deplasează de-a lungul acelor tranziții. Deci ceea ce vom face acum este să convertim nu DFA-urile în expresii regulate, ci vom converti GNFA-urile în expresii regulate. Este și mai greu, deoarece GNFA-urile sunt... vă permit să faceți tot felul de alte lucruri, în afară de DFA-urile obișnuite. Deci asta e o treabă mai grea. De ce îmi fac viața mai grea? Ei bine, vei vedea într- un minut că se va dovedi de fapt util să lucrezi cu un model mai puternic în modul în care această construcție va funcționa. Acum, înainte să mă scufund și să fac construcția de la GNFA la expresii regulate, voi face o presupunere simplificatoare despre GNFA. O să le pun într-o formă specială care va face mai ușor să faceți conversia. Și acea formă mai simplă este, în primul rând, voi presupune că GNFA are doar o singură stare de acceptare. Și acea stare de acceptare nu are voie să fie starea de început. Deci trebuie să aibă doar o singură stare de acceptare. Am încălcat deja această ipoteză convenabilă în acest GNFA, pentru că am aici două state care acceptă. Nu asta vreau. Vreau să am doar unul. Ei bine, chestia este că este ușor să obții doar una, doar să modific mașina astfel încât să am doar una, adăugând o nouă stare de acceptare care este ramificată de la fostele stări de acceptare prin tranziții goale. Așa că pot să sară oricând de la q2 la q4 în orice moment, fără măcar să citesc nicio intrare, mergând doar de-a lungul acestei tranziții goale. Și apoi declasific primele state acceptante ca fiind acceptante. Și acum am aici doar o singură stare de acceptare. Și pentru că va fi o stare nouă pe care am adăugat-o, nu va fi starea de început. Și am realizat acel aspect al presupunerii mele despre forma GNFA. Dar mai este un lucru pe care vreau să-l fac și eu. Vreau să presupun - după cum veți vedea, ceea ce va fi convenabil în construcția mea - că vom avea săgeți de tranziție care vor merge de la fiecare stare la orice altă stare. De fapt, vreau săgeți de tranziție care merg din fiecare stat chiar și înapoi la ei înșiși. Vreau să existe... toate săgețile de tranziție posibile ar trebui să fie prezente, cu două excepții. Pentru starea de pornire, ar trebui să existe doar săgeți de tranziție care ies din starea de pornire. Iar pentru starea de acceptare-- există doar una acum-- ar trebui să existe doar săgeți de tranziție care vin în starea de pornire. Deci este un fel de ceea ce v-ați imagina ca fiind rezonabil. Pentru celelalte state, care nu acceptă sau nu încep, ar trebui să existe săgeți de tranziție care pleacă și vin de peste tot. Dar pentru începutul statelor, doar plecarea. Și din starea de acceptare, tocmai intră. Și puteți modifica cu ușurință mașina pentru a realiza asta. Să vedem cum să facem asta într-un exemplu. Deci de la... observați că de la q3 la q2 nu există nicio tranziție în acest moment. Și asta nu e bine. Nu asta vreau. Vreau să existe o tranziție de la q3 la q2. Ei bine, voi adăuga doar acea tranziție. Dar o voi eticheta cu expresia regulată a limbajului gol. Deci asta înseamnă, da, tranziția este acolo, dar nu o poți accepta niciodată. Deci nu schimbă limba pe care mașina o va recunoaște. Dar îndeplinește ipoteza mea, ipoteza mea convenabilă, că toate aceste săgeți de tranziție sunt prezente în mașină. Deci oricum, sper sa il cumperi. Nu va fi... dacă nu înțelegi asta, nu-ți face griji. Nu este absolut esențial să urmați toate aceste mici ajustări și modificări ale GNFA. Dar va fi util să înțelegem ce GNFA în sine - cum funcționează. Deci, așa cum am menționat, putem modifica cu ușurință GNFA pentru a avea forma specială pe care o asumăm aici. Așa că acum vom interveni și vom începe să facem conversia. Deci vom avea o lemă, care este ca o teoremă care într-adevăr este doar de interes local aici. Nu este o teoremă de interes general. Va fi relevant doar pentru GNFA, care sunt într-adevăr doar definite pentru a ne ajuta să facem această conversie. Ele chiar nu au nicio altă valoare independentă. Deci fiecare... vrei să arăți că fiecare GNFA are o expresie regulată echivalentă R. Acesta este cu adevărat scopul meu. Și modul în care vom demonstra asta este prin inducție. Va fi prin inducție asupra numărului de state din GNFA. Acum, cu adevărat ar trebui să fii familiarizat cu inducția ca una dintre așteptările pentru a participa la acest curs. Dar în cazul în care sunteți puțin tremurând, nu vă faceți griji. O să-l despachetez ca procedură. Este într-adevăr doar recursivitate. Știi, inducția este doar... o dovadă care folosește inducția este de fapt doar o dovadă care se numește pe sine. Este doar o dovadă că... este o dovadă recursivă. Asta e tot. Deci, dacă vă simțiți confortabil cu recursiunea, vă veți simți confortabil cu inducția. Dar oricum, voi descrie asta ca pe o procedură. Deci, dacă sunteți puțin tremurător la inducție, nu vă faceți griji. Deci, baza este... așa că mai întâi mă voi ocupa de cazul în care GNFA are doar două state. Acum, amintiți-vă, presupun că acum GNFA-urile mele sunt în forma specială. Deci nu poți avea nici măcar un GNFA cu un singur stat, pentru că trebuie să aibă o stare de start și trebuie să aibă o stare de acceptare, iar ele trebuie să nu fie la fel. Deci, cel mai mic GNFA posibil de care să vă faceți griji este un GNFA cu două state. Acum, dacă avem un-- dacă se întâmplă să avem un GNFA cu două stări, se dovedește a fi foarte ușor să găsim expresia regulată echivalentă. De ce? Pentru că acel GNFA cu două state poate arăta doar așa. Poate avea o stare de pornire, poate avea o stare de acceptare și poate avea doar o tranziție de la început la acceptare, deoarece nu sunt permise alte tranziții. Are doar ieșiri de la început, doar intrari de la... până la acceptare. Și deci există o singură tranziție. Și are o etichetă cu o expresie regulată R. Deci, ce crezi că este expresia regulată echivalentă pentru acest GNFA? Este pur și simplu cel care etichetează această tranziție, pentru că asta ne spune când pot trece de la început până la acceptare. Și aparatul nu mai poate face nimic. Face doar un pas, care este să-și accepte intrarea dacă este descrisă de acea expresie regulată. Prin urmare, expresia regulată echivalentă pe care o căutăm este pur și simplu eticheta pe acea singură tranziție. Deci GNFA în două etape sunt ușoare. Dar dacă... ce se întâmplă dacă ai mai multe state? Atunci va trebui să faci ceva de lucru. Așa că numim asta pasul de inducție. Atunci avem mai mult de două state. Și așa-- modul în care funcționează inducția este că vom presupune că știm deja cum să o facem pentru k minus 1 stări. Și vom folosi aceste cunoștințe pentru a arăta cum să o facem pentru k stări. Deci, cu alte cuvinte, știm deja cum să o facem pentru două stări. Voi folosi acest fapt pentru a arăta cum să o fac pentru trei stări și apoi să folosesc faptul că o pot face pentru trei stări pentru a arăta cum să o fac pentru patru stări și așa mai departe, și așa mai departe. Și ideea cum să faci asta este de fapt destul de ușor de înțeles. Ceea ce vom face este că, dacă avem o stare k GNFA pe care dorim să-l convertim, vom schimba acea k stare GNFA la un k minus 1 stare GNFA și apoi să folosim presupunerea că știm deja cum să facem k minus 1 stare GNFA. Deci, în ceea ce privește o imagine, voi lua o stare k -- pentru a dovedi că pot întotdeauna converti GNFA cu stări k în expresii regulate, voi arăta cum să convertesc starea k una într-un echivalent k minus 1 GNFA de stat. Și apoi, dacă îți place să te gândești la asta din punct de vedere procedural, k minus 1 este convertit într-un k minus 2, este convertit într-un k minus 3 și așa mai departe, și așa mai departe, până ajung la doi, ceea ce atunci știu. cum se face direct. Deci, întregul nume al jocului de aici este să descopere cum să convertești un GNFA care are k stări într-un altul care are o stare mai puțin care folosește aceeași limbă. Deci trebuie să ții asta în cap. Adică, mi-aș dori să am mai mult spațiu pe tablă aici, dar aici este foarte limitat. Așa că trebuie să vă amintiți ce vom face în următorul diapozitiv, pentru că asta va termina treaba pentru noi. Atâta timp cât pot arăta, în general, cum să convertesc un K, GNFA de stat într-un GNFA care are o stare mai puțin, dar încă face același limbaj, sunt bine, pentru că atunci pot continua să repet asta până ajung la două. . Așa că iată-- acesta este curajul argumentului. Deci am mașina mea de k state. Iată starea mea de început. Iată starea mea de acceptare. Iată starea mea k minus 1 , acea mașină pe care o voi construi pentru tine. De fapt, va fi... să arate aproape exact la fel. Voi elimina doar o stare din mașina mai mare. Deci voi alege orice stare care nu este starea de pornire sau starea de acceptare. Aici este pozata aici. Adică, toate stările mașinii de stări k vor apărea în mașina de stări k minus 1, cu excepția unei stări pe care o voi smulge. Aceasta este starea x. Acum este aici ca o fantomă. A fost eliminat. Nu mai este acolo. Dar te ajut doar să-ți amintești că a fost acolo, arătând această umbră. Dar este o... Mi-am luat mașina mea originală care avea k stări și practic tocmai am smuls o stare. Și acum am un stat mai puțin. Deci, vestea bună este că acum am o mașină cu k minus 1 stări. Asta vreau. Dar vestea proastă este că nu mai vorbește același limbaj. Am spart mașina prin rupere... dacă doar ai de gând să distrugi o stare, cine știe ce va face noua mașină. Probabil că nu va fi la fel cu ceea ce a făcut mașina originală. Deci, ceea ce trebuie să fac, atunci, este să repar deteriorarea. Trebuie să repar daunele pe care le-am cauzat prin eliminarea x. Și oricare ar fi rolul jucat de x în mașina originală, trebuie să mă asigur că noua mașină pe care o am, care nu mai are x, poate face în continuare aceleași lucruri pe care le-a făcut mașina originală. Și așadar, modul în care voi face asta este să mă uit la toate căile care ar putea trece prin x și să mă asigur că sunt încă prezente, deși nu mai am x. Și felul în care voi face asta este, voi lua-- luați în considerare o parte a unei căi care ar putea folosi x. Deci începe-- să alegem două stări, qi și qj, în mașina care a avut k stări. Lasă-mă să văd aici... Nu știu dacă asta... OK. Avem-- dacă avem-- vom alege două stări, qi și qj, în mașina originală. Acum, qi ar putea avea posibilitatea de a trece la starea x. Și apoi x ar putea avea o buclă de sine. Și apoi ar putea merge la qj. Noua mașină nu mai are un x. Modul în care voi remedia acest lucru este prin înlocuirea etichetei care merge direct de la i la j cu o nouă etichetă care adaugă toate lucrurile pe care le- am pierdut când am eliminat x. Asta e toată ideea aici. Deci aici este qi la qj, dar nu mai există x. Cum aș putea ajunge de la qi la qj? Care au fost intrările care ne-ar fi putut aduce de la qi la qj prin x? Ei bine, ar fi fost o intrare care a citit un șir descris de r1. S- ar putea să mă fi uitat de câteva ori la x, așa că s-ar putea să fi citit mai multe șiruri care sunt descrise de r2. Și apoi aș fi citit un șir care a fost descris de r3. Și acum sunt la qj. Așadar, noua etichetă pe care o voi plasa aici va fi șirurile pe care le primesc din citirea r1 -- citirea unui șir descris de r1, apoi mai multe copii ale șirurilor -- mai multe șiruri care, posibil, descriu r2, care este la fel cu stea r2. Oh, și apoi multipli-- și apoi un șir care ar putea fi descris de r3. Deci aceasta este o nouă adăugare la tranziția care mă duce de la qi la qj. Desigur, trebuie să includ în primul rând lucrurile care m-ar fi dus de la qi la qj. Deci mă unesc și în r4, care este ruta directă de la qi la qj care nu a tranzit prin x. Deci, făcând acea nouă expresie regulată pe tranziția qi la qj, am compensat pierderea lui x pentru căile care merg de la qi la x și apoi la qj. Acum, ceea ce trebuie să fac este să fac același lucru pentru fiecare pereche qi și qj care se află în mașina originală. Și deci, dacă fac asta pentru fiecare pereche posibilă, voi modifica toate tranzițiile din noua mașină într-un mod care să compenseze pierderea lui x. Și acum noua mașină a fost reparată din cauza daunelor pe care le-am provocat prin îndepărtarea x. Și face același limbaj. Este genul de lucru la care trebuie să te gândești puțin. Am înțeles. Dar, cel puțin , sperăm că spiritul a ceea ce tocmai v-am descris vine prin faptul că vom converti această mașină k-- cu k stări într- una cu k minus 1 stări prin eliminarea unei stări și repararea daunelor. Și acum face același limbaj. Și apoi pot elimina o altă stare și pot face același lucru iar și iar până ajung la două stări. Deci asta e ideea. Și asta completează cu adevărat dovada. Asta arată că pot converti fiecare GNFA într-o expresie regulată. Și acesta este într-adevăr sfârșitul poveștii pentru asta. Și astfel susțin că DFA, acum, și expresiile regulate sunt echivalente. Așa că lasă-mă... o să-ți fac o mică verificare aici, doar ca să văd, la nivel înalt, dacă urmărești ce se întâmplă. Așa că aruncați o privire. Așa că tocmai am arătat cum să convertim GNFA-urile în expresie regulată. Dar ne-am dorit foarte mult să transformăm DFA în expresii regulate. Deci, cum trecem de la GNFA-- conversia GNFA la conversia DFA? Pentru că nu sunt la fel, evident. Dreapta? Deci cum terminăm asta? Deci aici sunt trei variante. În primul rând, trebuie să arătăm cum să convertim DFA în GNFA, poate? Sau arătați cum să convertiți GNFA în DFA? Sau poate am terminat deja? Așa că poate mai bine lansez acel sondaj în timp ce citești asta. Și iată. Sper că poți... în regulă. De ce nu termin asta? Este puțin îngrijorător, pentru că aș spune că avem o pluralitate care a primit răspunsul corect, dar nu o majoritate. Deci haideți să împărtășim rezultatele. Cred... deci simt că nu toți sunteți cu mine. Dar va trebui să-- fie asta, fie te joci-- îți citești e- mailul în timp ce vorbim. Nu sunt sigur. Dar orice ar fi, trebuie să te gândești puțin la ce se întâmplă aici, pentru că motivul pentru care am terminat este că DFA-urile sunt un fel de GNFA. Sunt doar... au un tip foarte simplu de expresie regulată la fiecare tranziție. Au doar expresia regulată care este doar un singur simbol. Deci, toate DFA sunt automat GNFA. Deci, dacă pot converti GNFA-urile, cu siguranță pot converti DFA-urile, deoarece GNFA-urile includ DFA-urile. Am terminat. Într- adevăr a fost... numărul C a fost răspunsul corect. Așa că bine că nu [râde] numărăm corectitudinea aici. Deci participarea este suficient de bună. Dar cred că trebuie să te gândești la ce se întâmplă și să te asiguri că urmărești. Deci, oricum, asta e... vom continua aici. Dar mă face puțin îngrijorat. Deci haideți să trecem mai departe. Așa că vom vorbi puțin despre limbile neobișnuite. Deci cineva întreabă, nu trebuie să facem în continuare DFA-urile în tipul special? Da, trebuie să le facem la tipul special. Dar am arătat deja cum să transformăm GNFA în tipul special. Și DFA-- asta se va aplica și DFA-urilor. Vor deveni GNFA. Puteți adăuga pornirile suplimentare-- adăugați o nouă stare de pornire, adăugați o nouă stare de acceptare, adăugați toate tranzițiile cu-- pe care nu le aveați înainte cu eticheta de limbă goală și veți avea un GNFA de la un DFA. Dar asta se aplică GNFA-urilor ca... în general. Deci, nu este nimic special la DFA acolo. Oricum, cred că trebuie să mesteci asta. Și sperăm că tu... vei urmări în continuare. Oricum, haideți să ne uităm acum la non-- dovedirea neregularității. Așa că am terminat cu obiectivul nostru de a arăta că limbajele obișnuite -- că limbajele obișnuite pot proveni fie din DFA, fie din expresii regulate. Acestea sunt aceleași în ceea ce privește... din perspectiva cursului nostru, sunt interschimbabile. Așa că acum, așa cum am menționat, vor exista unele limbi care nu sunt obișnuite, care nu pot fi făcute de către DFA. Ei sunt de fapt... DFA-urile sunt de fapt destul de slabe ca model de calcul. Și așa că există tot felul de lucruri foarte simple pe care ei nu le pot face -- deși există câteva lucruri destul de complicate pe care le pot face, în mod surprinzător. Dar oricum, există câteva lucruri simple pe care nu le pot face. Așa că trebuie să dezvoltăm o metodă pentru a arăta că o limbă nu este obișnuită. Și asta va fi util pentru temele și, în general, doar pentru a înțelege puterea DFA-urilor. Deci, cum arătăm că o limbă nu este obișnuită? Așa că nu uitați, dacă doriți să arătați că o limbă este obișnuită, practic ceea ce trebuie să faceți este să oferiți un DFA. Sau puteți utiliza proprietățile de închidere. Acesta este un alt mod de a arăta că o limbă este obișnuită. Dar, dedesubt, se construiește DFA-uri. Pentru a arăta că o limbă nu este obișnuită, trebuie să dai o dovadă. În general, nu este o construcție, este o dovadă că nu există DFA sau orice altceva-- că va fi imposibil să faci un DFA. Și trebuie să dezvoltăm o metodă. Care este metoda aia de demonstrare? Acum, există o tentativă... știi , am predat acest curs de multe ori și există o abordare tentantă pe care mulți oameni o au. Nu se va aplica doar pentru automate finite, ci și pentru alte lucruri. Și credeți-mă, nu sunt doar oamenii din această clasă, ci sunt pentru cei din-- care încearcă să se gândească la calcul în general-- adică, ei bine, am ceva limbaj. Încerc să-mi dau seama dacă este normal sau nu. Și așa m-am gândit foarte bine cum să fac un DFA și nu am putut găsi unul. Prin urmare, nu este obișnuit. Asta nu este o dovadă. Doar pentru că nu ați putut găsi un DFA nu înseamnă că nu există DFA. Trebuie să dovediți că limbajul nu este obișnuit folosind o metodă. Așa că am să vă dau un exemplu în care acest tip de abordare vă poate duce greșit. Și asta este... Voi da două exemple de limbi în care ați putea încerca să dovediți că sunt obișnuite sau nu și ați putea avea probleme dacă doar urmați acest tip de abordare informală. Deci, dacă luați limba B, unde acestea sunt șiruri - ei bine, să presupunem că alfabetul nostru este zero și unu. B este limbajul tuturor șirurilor care au un număr egal de zerouri și unu. Deci vrei să știi, dacă am 1.000 de zerouri, trebuie să am 1.000 de unități. Deci, practic, în felul în care testați asta, ar trebui să numărați numărul de zerouri, să numărați numărul de unități și să vedeți dacă cele două numărări sunt la fel. Și va fi foarte greu să-l faci pe un DFA, pentru că cum vă veți aminti așa-- acel număr foarte mare de zerouri care-- DFA ar putea avea 50 de state. Dar ar putea fi nevoie să numeri până la 100 sau un milion pentru a-ți da seama... pentru a număra câte zerouri ai văzut. Și pare foarte greu să poți face un asemenea număr atunci când ai doar 50 de stări. Deci, indiferent de numărul de stări pe care le aveți, pare greu de numărat când aveți un automat finit. Deci intuiția este că nu este obișnuit pentru că un automat finit nu poate conta. Pe care, în acest caz, puteți converti acea intuiție într-o dovadă reală. Aș spune că nu este încă o dovadă reală, dar poate fi transformată într-o dovadă reală. Dar compară acel caz cu un alt limbaj, pe care îl voi numi C, care, în loc să mă uit la intrarea sa pentru a vedea dacă are un număr egal de zerouri și unu, mă voi uita la intrare și mă voi uita la subșiruri. de 01s și 10s-- acele două subșiruri-- și numărați numărul de apariții ale lui 01 ca subșir și numărul de apariții ale lui 10 ca subșir. Doar pentru a ne asigura că înțelegeți, să ne uităm la câteva exemple -- două exemple. Deci șirul 0101 nu va fi în C, pentru că dacă numărați numărul de 01 și numărul de 10, nu este același lucru. Așa că chiar o să te ajut aici, dacă vezi asta. Numărul 01 este doi. Dar există doar o singură apariție de 10. Deci acelea sunt... acele două numărări sunt diferite. Și de aceea acest șir de intrare nu este în C. Comparați-l cu șirul 0110. Acum, dacă numărați numărul de subșiruri 01 și 10, veți obține aceeași valoare, deoarece aici avem un singur 01 și un singur 10. Și așa că acum cele două numărări ale acelor număr de subșiruri sunt aceleași. Și deci acolo te afli în C. Acum întrebarea mea este, C este un limbaj obișnuit? Ei bine, se pare că nu ar trebui să fie obișnuit din același motiv pentru care B nu este obișnuit -- pentru că trebuie să numărați două cantități și să le comparați. BINE? Deci, acum, deci dacă noi... deci aceasta este intuiția noastră, că pur și simplu nu o poți face pentru... cu un automat finit, pentru că trebuie să faci același tip de numărare pe care ar fi trebuit să-l faci pentru limba B. Dar aici vei fi... ai greși, pentru că C, de fapt, este obișnuit. Are o descriere mult mai simplă decât cea pe care am dat-o aici la început. Același limbaj, C, poate fi descris într-un mod mult, mult mai simplu. Nu am de gând să- ți spun ce este. Poți să te gândești la asta. Puteți încerca câteva exemple pentru a vă da seama. Dar are o descriere mult mai simplă. Nu este o descriere total banală. Există ceva conținut acolo. Dar există... este genul de lucru pe care îl poate face un automat finit. Nu ar face numărătoarea în acest fel. Deci morala este că, uneori, intuiția funcționează, dar poate fi și greșită. Și deci morala poveștii este că trebuie să dai o dovadă când faci așa ceva. Deci, ceea ce vom face în continuare, în a doua jumătate a prelegerii, este să oferim o metodă pentru a demonstra că limbile nu sunt obișnuite. Și din nou, va trebui să-l folosești la teme. Așa că sper să înțelegi. Dar, în primul rând, nu am încetat niciodată să distribui acel sondaj. Iartă-mă. Și, cu asta, cred că ne vom lua mica noastră pauză cerută. Și... timp de cinci minute. Și ne întoarcem în cinci minute. Deci, timp de pauză. Am terminat aici. Și dovedind că limbile nu sunt obișnuite. Modul în care vom demonstra că limbajele nu sunt obișnuite este prin introducerea unei metode numită lema de pompare. Și planul general la lema de pompare, fără a intra în specificul acesteia, este să spunem -- arătați că -- acea lemă spune că toate limbajele obișnuite au o anumită proprietate, pe care o vom descrie. Și astfel, pentru a arăta că o limbă nu este obișnuită, pur și simplu arăți că limba nu are această proprietate, deoarece toate limbile obișnuite trebuie să aibă această proprietate. Și astfel, arătând că o limbă nu are proprietatea, nu ar putea fi obișnuită. Acesta este planul. Acum, proprietatea în sine este puțin complicat de descris, dar nu prea rău. Voi încerca să-l despachetez pentru tine. Dar mai întâi, să ne uităm la declarația lemei, care spune că ori de câte ori ai un limbaj obișnuit -- să-l numim A. Deci, pentru fiecare limbaj obișnuit A există întotdeauna o valoare specială numită pompă -- un număr. p, o vom numi-- numită lungimea de pompare. Este un număr special. Și este... și acea lungime vă spune că ori de câte ori un șir este în limba respectivă și este mai lung decât acea lungime, atunci se întâmplă ceva special. Puteți lua acel șir și îl puteți modifica și rămâneți în continuare în limba. Așadar, orice este mai lung decât acea lungime specială poate fi modificat într-un anumit fel și rămâneți în continuare în limbă. Deci, să ne uităm la declarația reală a lemei. Deci, există un număr p astfel încât, dacă s este un șir în limbaj și este mai lung decât p, sau cel puțin de lungime p, atunci puteți lua s și îl puteți tăia în trei bucăți -- x, y și z-- deci este doar împărțirea s-ului în trei bucăți-- unde poți lua piesa din mijloc, o poți repeta de câte ori vrei și vei rămâne în limbă. Asta e... ceea ce spune lema de pompare. Și există o grămadă de alte condiții și aici. Dar spiritul lemei de pompare spune că, ori de câte ori ai un limbaj obișnuit, există o tăietură, astfel încât toate șirurile mai lungi decât acel cutoff pot fi ceea ce numim pompate. Puteți lua acel șir, puteți găsi o secțiune undeva în mijlocul acelui șir sau undeva -- o tăiați în trei bucăți, luați piesa centrală și o puteți repeta. Îl poți pompa. Și prin repetarea acelui șir și repetarea acelei piese, șirul devine din ce în ce mai lung. Dar tot rămâi în limbă. Aceasta este proprietatea specială pe care o au toate limbile obișnuite. Deci, într-un mod informal, și vom face, voi încerca să vă ajut să simțiți asta. Informal, se spune că, dacă aveți un limbaj obișnuit, atunci fiecare șir lung -- deci un lung este prin -- un mod informal de a spune mai mare decât această valoare p. Fiecare șir lung din limbă poate fi pompat. Și acest rezultat rămâne încă în limbă. Și prin „pompat” pot tăia sfoara în trei bucăți și repet piesa din mijloc de câte ori vreau. Asta vreau să spun prin pomparea unei sfori. Așa că vom face câteva exemple într-o secundă. Dar mai întâi vom vedea cum să dovedim acest lucru. Și, sperăm, că asta vă va da o senzație, de asemenea, de ce este adevărat. Deci... și de fapt, poate înainte să trec cu adevărat în dovezi, permiteți-mă... să ne uităm la aceste trei condiții aici doar pentru a le înțelege puțin mai detaliat. Deci, un fel de condiție spune ceea ce tocmai ți-am spus. Pot să rup s-ul în trei bucăți-- x, y, z-- astfel încât dacă duc x y la i z-- așa că se repetă y de câte ori vreau. Așa că iată y la definiția i, dacă asta vă este de ajutor... sunt doar y-- i copii ale lui y. Deci pot duce x y la i z și rămân în limbaj pentru fiecare valoare a lui i-- chiar și i este egal cu 0, ceea ce înseamnă că doar eliminăm y, ceea ce uneori este de fapt un lucru util de făcut. Dar să nu trecem înaintea noastră. Deci, dacă... știi, pot tăia s-- Sunt garantat că voi putea tăia s în x, y, z, astfel încât șirul xyyy să fie încă în limbă, sau xyyyyy-- este încă în limbă . Acest lucru va fi garantat pentru fiecare limbă obișnuită. Aceasta este o caracteristică care va fi adevărată. Și, în plus, și asta se va dovedi a fi, nu face parte din ideea de bază a lemei de pompare, dar de fapt se dovedește a fi foarte util în aplicarea lemei de pompare. Îl puteți tăia oricând astfel încât primele două bucăți să nu fie mai lungi decât valoarea p. Deci asta... limitează modurile în care poți tăia chestia. Și asta se dovedește de fapt a fi de mare ajutor. Dar să ne uităm mai întâi la dovada acestui lucru, oferind puțin imaginea la nivel înalt. Așa că treaba mea este să arăt, dacă am un șir în limba mea - să spunem că este un -- gândiți-vă la el ca pe un șir lung, foarte lung. Deci lungimea sa este mai mare de p. Dar cred că intuitiv, este doar un șir foarte lung. Și voi introduce acel șir în aparat și voi urmări ce se întâmplă. Se întâmplă ceva special când alimentez sfoara și mă uit la modul în care mașina procedează pe acel șir, pentru că s este atât de lung încât, pe măsură ce mă plimb în interiorul mașinii, trebuie să ajung să mă întorc în același loc de mai multe ori. Este ca și cum ai avea un mic parc și te duci la o plimbare lungă. Vei sfârși prin a te întoarce acolo unde ai... ceea ce ai văzut deja. Pur și simplu nu poți continua să vezi lucruri noi atunci când ai o zonă mai mică de spațiu de explorat. Prin urmare, suntem garantați că M va ajunge să repete o stare când citește s, deoarece s este atât de lung. Deci, în termeni-- pictorial, dacă vă imaginați aici această linie ondulată descrie calea pe care M o urmează când citește s, ajunge să revină la acea stare qj de mai multe ori. Așa că se întoarce aici, circulă, revine din nou înainte de a ajunge să accepte. Știm că ajunge să accepte pentru că presupunem că avem un șir care este în limbaj. Așa că am ales s în limbă. Deci trebuie acceptat de M. Dar important este că repetă o stare. Acum, cum îmi spune asta că pot tăia în acele trei bucăți? Ei bine, voi lua cele trei bucăți aici. În primul rând, să observăm că aici este procesarea-- ca procesare s. Iată-- scris chiar deasupra șirului, acea stare de repetiție având loc, qj, de mai multe ori. Și acum, dacă mă uit în interiorul mașinii, partea lui s care m-a dus la qj o voi suna pe x. Partea care m-a dus de la qj înapoi la sine o voi numi y. Și partea care l-a dus pe qj la starea de acceptare o voi numi z. Și le voi marca pe acelea în s. Și asta îmi oferă modalitatea de a tăia în trei bucăți. Acum, dacă apreciați ce se întâmplă în interiorul mașinii, veți vedea de ce M va accepta și șirul xyyz-- pentru că de fiecare dată-- odată ce sunteți la qj, dacă mergeți o dată, vă întoarceți la qj . Și apoi, dacă te duci din nou, te vei întoarce la qj. Și de câte ori vei continua să vezi acel y, vei continua să revii la qj. Deci nu contează câți y ai. Veți continua -- dacă îl urmați de z, ceea ce veți face -- veți ajunge să acceptați acest șir. Și asta este cu adevărat dovada. Adică, trebuie să faci puțin mai mult aici doar pentru a înțelege-- Ar fi trebuit să menționez de ce vreau să interzic y să fie șirul gol, pentru că dacă y este șirul gol, nu este interesant. Nu se schimbă, repetarea nu schimbă nimic. Așa că trebuie să mă asigur că nu este gol. Dar oricum, acesta este un detaliu aici. Dacă te uiți la șirul xyyz, asta va fi totuși acceptat. Deci aceasta este dovada lemei de pompare. Deci, să facem un mic check-in legat de asta. Acest lucru nu va fi... din nou, nu foarte greu. Dar mai mult doar o curiozitate. Deci lema de pompare depinde de faptul că, dacă M are p stări și rulează pentru mai mult de p pași, atunci va intra într-o stare de două ori. Deci poate ai mai văzut asta înainte. Are de fapt un nume pe care unii dintre voi poate l-ați văzut. Deci, să vedem cum să obținem un sondaj aici. Și sper că nu prea mulți dintre voi veți alege C, deoarece este... unii dintre voi. [Râde] Ei bine. Da, cred că acesta majoritatea dintre voi sunteți... ați mai văzut asta înainte. Aceasta este... Cred că aproape toți ați înțeles-o. Acesta este ceea ce este cunoscut sub numele de Principiul Porumbeilor. Deci, iată, împărtășind rezultatele, evident că mă distram puțin cu asta. Sunt sigur că unii dintre voi v- ați distrat cu mine. Asta e ok. Deci hai să continuăm. Să vedem cum să folosim lema de pompare pentru a demonstra că o limbă nu este obișnuită. Așa că am pus lema de pompare aici, ca să vă amintiți afirmația ei. Deci, să luăm limbajul D, care este limbajul 0 la k 1 la k pentru orice k. Deci, acesta este un număr de zerouri urmat de un număr egal de unu. Vom demonstra că limbajul nu este obișnuit folosind lema de pompare. Și aceasta va fi doar o dovadă de fier. Nu va spune, ei bine, nu m-am putut gândi cum să... Nu m-am putut gândi cum să-i găsesc un automat finit. Aceasta va fi... aceasta va fi cu adevărat o dovadă. Deci vrem să arătăm că D nu este regulat. Și vom da... aceste lucruri merg întotdeauna ca o dovadă prin contradicție. Deci, dovadă prin contradicție -- sperăm, ca o reamintire pentru tine, modul în care funcționează este că vei presupune opusul a ceea ce încerci să demonstrezi. Și apoi din asta, ceva nebunesc se va întâmpla, ceva despre care știi că este evident fals sau greșit. Prin urmare, presupunerea ta, care este opusă a ceea ce încercai să demonstrezi, a trebuit să fie greșită. Prin urmare, lucrul pe care încerci să-l dovedești trebuie să fie corect. Aceasta este esența a ceea ce se numește dovezi prin contradicție. Deci, în primul rând, vom presupune, pentru a obține contradicția noastră, că D este regulat, ceea ce încercăm să arătăm că nu este cazul. Acum, dacă D este regulat, atunci putem aplica lema de pompare de mai sus aici, care ne oferă acea lungime de pompare p, care spune că orice șir mai lung decât p poate fi pompat și rămâneți în limbaj. Asta vă spune lema de pompare. Deci, să alegem șirul s, care este șirul de la 0 la p 1 la p. Iată un fel de poză cu s off pe partea laterală. Deci o grămadă de zerouri urmate de un număr egal de unu. Și acel șir este în D pentru că D este șiruri de acea formă. Și este mai lung decât p. Evident, are lungimea de 2p. Așadar, lema de pompare ne spune că există o modalitate de a o reduce satisfăcând acele trei condiții. Deci, cum naiba am putea să le tăiem? Ei bine, amintiți-vă de cele trei condiții. Și mai ales condiția 3 va fi utilă aici. Spuneți că puteți tăia s-ul în trei bucăți-- x, y și z-- unde primele două bucăți se află în primele p simboluri ale lui s cel mult p lung. Deci, x și y împreună nu sunt foarte mari. Ele nu se extind dincolo de prima jumătate a lui x-- prima jumătate a lui s. Și în special, toate sunt zerouri. x și y vor fi toate zerouri. z va avea, probabil, niște zerouri și va avea restul celor-- le va avea pe cele. Acum, lema de pompare spune că dacă o tăiați astfel, puteți repeta y de câte ori doriți și rămâneți în limba. Dar asta este evident fals, pentru că dacă repeți y-- care acum are doar zerouri-- vei avea prea multe zerouri. Și astfel șirul rezultat nu va mai fi de forma 0 la k 1 la k. Vor fi multe zerouri urmate de nu atât de multe. Asta nu este în limbă. Și asta încalcă ceea ce lema de pompare spune că ar trebui să se întâmple. Și asta e o contradicție. Prin urmare, presupunerea noastră că D este regulat este falsă. Și astfel concluzionăm că D nu este regulat. Deci este unul destul de simplu. M-am gândit să mai fac câteva exemple, pentru că ai asta pe teme și m-am gândit că ar putea fi de ajutor. Așa că iată-l pe al doilea... puțin mai greu, dar nu prea mult. Să luăm limbajul F, care este... arată ca ww-ul șirului. Acestea sunt șiruri care... două copii ale aceluiași șir. Pentru orice șir care ar putea fi în stea sigma, deci pentru orice șir , voi avea două copii ale acelui șir. Și deci F este acele șiruri care pot fi-- care sunt doar două copii ale aceluiași șir. Vom arăta că F nu este obișnuit. Aceste lucruri merg întotdeauna în același mod. Este același model. Demonstrezi prin contradicție. Așa că presupui pentru contradicție că... oh, D. Asta e rău. A fost copiat de pe celălalt slide al meu. Este gresit. Să vedem dacă pot face asta să funcționeze aici. Bun. Presupunem pentru contradicție că F este regulat. Lema de pompare dă F ca mai sus. Și acum trebuie să alegem un șir s care este în F pentru a face pomparea și a arăta că lema de pompare va eșua. Veți pompa și veți obține ceva care nu este în limbă, care este-- arată că pompa-- ceva a mers prost. Dar pe care să alegi? Și, uneori, aici intervine creativitatea în aplicarea lemei de pompare, pentru că trebuie să-ți dai seama care este coarda potrivită pe care o vei pompa. Deci ați putea încerca șirul - ei bine, 0 la p 0 la p. Asta este cu siguranță în F. Sunt două copii ale aceluiași șir. Iată-l. Am scris o mulțime de zerouri urmate de același număr de zerouri. Problema este că, dacă folosești acel șir, este de fapt un șir pe care îl poți pompa. Poți rupe sfoara aceea în trei bucăți. Și apoi, dacă lași y să fie șirul 00-- de fapt, trebuie să fii puțin atent. Șirul doar 0 nu funcționează, pentru că aici are loc un fenomen de egalitate-ciudățenie . Așa că poate vrei să te gândești doar la asta. Dar dacă lăsați y să fie șirul 00, atunci dacă aveți șirul xy-- x orice număr de y-- tot va fi doar o grămadă de zerouri. Și veți putea vedea că acel șir este încă în limbă. Deci nu ai invatat nimic. Dacă lema de pompare funcționează și satisfaceți lema de pompare, nu ați învățat nimic. Deci, ceea ce trebuie să găsiți este un alt șir. A fost o alegere proastă pentru s. Găsiți un șir diferit. Deci, iată o alegere diferită, de la 0 la p 1 0 la p 1. Deci sunt două copii ale aceluiași șir. Și vei arăta că nu poate fi... vom arăta că nu poate fi pompat. Deci, iată o imagine a acelui șir aici. Deci zerouri urmate de 1, zerouri urmate de 1. Și acum este foarte asemănător cu primul argument. Dacă îl tăiați în trei bucăți în așa fel încât să îndeplinească condițiile, primele două bucăți vor locui doar printre zerouri. Prin urmare, atunci când repeți un y, nu vei mai avea două copii ale aceluiași șir. Și așa nu va fi în limbă. Prin urmare, aveți o contradicție și F nu este regulat. Deci trebuie să te joci puțin cu lema de pompare. Dacă nu ai văzut asta înainte de a fi... este nevoie de puțin să te obișnuiești. Dar aveți câteva întrebări legate de teme care trebuie rezolvate folosind lema de pompare. Deci, acum, să ne uităm la -- în sfârșit, există o altă metodă care poate apărea, care este combinarea proprietăților de închidere cu lema de pompare. Deci proprietățile de închidere vă ajută uneori. Deci, să ne uităm la limbajul B, care este, de fapt, pe care l-am văzut mai devreme în prelegere, unde avem un număr egal de zerouri și unu. Acum, am putea demonstra că în mod direct, folosind lema de pompare, ca nefiind regulat. Dar de fapt este și mai ușor. Ceea ce vom demonstra... că... vom demonstra că nu este obișnuit într-un mod diferit. În primul rând, vom presupune pentru contradicție, așa cum facem adesea, că este obișnuită. Și acum vom folosi ceva... vom folosi și alte cunoștințe. Nu vom folosi aici lema de pompare pentru că vom profita de un caz anterior în care am folosit lema de pompare. Și acum știm că șirul-- limbajul 0 stea 1 stea este un limbaj obișnuit, deoarece este descris printr-o expresie regulată. Dacă luați B, care este numere egale de zerouri și unu, și îl intersectați cu 0 stea 1 stea, acesta va fi un limbaj obișnuit dacă B a fost obișnuit, folosind închiderea sub intersecție. Dar acest limbaj B intersectează 0 stea 1 stea este limbajul numerelor egale de zerouri și a celor în care zerourile vin pe primul loc. Și aceasta este limba D pe care am arătat două diapozitive înapoi, despre care știm deja că nu poate fi obișnuită. Deci intersecția respectivă nu poate fi obișnuită. Și astfel încalcă proprietatea de închidere. Și din nou, avem o contradicție. Deci, acesta este un mod diferit de a face uneori o comandă rapidă pentru a demonstra că o limbă nu este obișnuită. Deci avem... în ultimele noastre 10 minute sau cam asa ceva, vom schimba vitezele complet, într-un mod complet diferit , și vom lua în considerare un nou model de calcul, care este mai puternic, care poate face lucruri pe care noi nu le putem face. face cu automate finite. Și acestea se numesc gramatici fără context. Deci aceasta este de fapt doar o introducere. Vom petrece toată prelegerea următoare analizând gramaticile fără context și limbile asociate acestora. Dar haideți să facem... obțineți o previzualizare. Deci, o gramatică fără context arată astfel. Aveți o grămadă de acestea-- ceea ce numim reguli de substituție, sau reguli, uneori, care arată ca un simbol, săgeată, un șir de simboluri. Așa arată o gramatică fără context la un nivel înalt. Să definim câțiva termeni. Deci, o regulă, așa cum tocmai am descris-o, va fi - uite-- va fi un simbol, pe care îl vom numi o variabilă. Și asta va avea o săgeată la un șir de alte -- eventual, alte variabile și simboluri numite terminale. Deci, o variabilă este un simbol care apare în partea stângă a unei reguli. Orice apare în partea stângă va fi considerat a fi o variabilă. Deci S și R sunt ambele variabile. Acum, alte simboluri care apar în gramatică și care nu apar în partea stângă - acestea vor fi numite terminale. Deci aici, 0 și 1 sunt terminale. Acum, puteți crede că șirul gol ar trebui să fie și un terminal . Dar asta nu este un simbol. Șirul gol este un șir. Este doar un șir de lungime 0. Deci nu consider șirul gol ca un terminal. Deci... și apoi va exista o variabilă specială care va fi considerată variabila de pornire, la fel cum am avut o stare de pornire. Și acesta va fi de obicei scris ca simbolul din stânga sus. Deci, acest simbol s, aici, va fi simbolul de pornire. Și gramaticile pot fi folosite pentru a defini limbi și pentru a-- ei bine, pentru a genera șiruri și pentru a defini limbi. Deci, în primul rând, să vedem cum o gramatică, folosind asta ca ilustrație, poate genera șiruri. De fapt, doar pentru a sublinia această terminologie aici, în acest exemplu special am avut trei reguli. Cele două variabile au fost R și S. Cele două terminale au fost 0 și 1. Și variabila de început a fost acest simbol din stânga sus, așa cum am menționat -- S. Deci gramaticile generează șiruri. Modul în care fac ei este să urmezi o anumită procedură, care este într-adevăr destul de simplă. Scrieți, în primul rând , variabila de start. Și voi face un exemplu într-o secundă. Notați variabila de început. Și apoi te uiți la ce ai scris. Și dacă are variabile în ea, puteți aplica una dintre părțile din dreapta corespunzătoare ale unei reguli ca o substituție pentru acea variabilă. Și așa-- cum ar fi, de exemplu, dacă aveți un S în lucrul pe care l-ați notat, puteți înlocui acel S cu 0S1. Sau puteți înlocui acel S cu R. Sau dacă aveți un R, puteți înlocui S cu un șir gol. Așa că veți continua să faceți acele înlocuiri din nou și din nou până când nu vor mai rămâne variabile, așa că nu mai rămâne nimic de înlocuit. Rămân doar terminalele. În acel moment, ați generat un șir în limbaj. Deci, limbajul este colecția tuturor șirurilor generate. Să facem un exemplu. Iată un exemplu de G1 care generează un șir. Așa că, așa cum am menționat, mai întâi de toate, veți nota variabila de pornire. Și voi ilustra acest lucru în două piese paralele aici. În partea stângă am să vă arăt arborele substituțiilor. Și în partea dreaptă vă voi arăta șirul rezultat pe care îl obțineți aplicând acele substituții. Deci aici voi înlocui S cu șirul 0S1. Așa că în partea dreaptă am doar 0S1, pentru că asta am înlocuit S. Dar vei vedea că nu va-- va arăta puțin diferit într-o secundă. Aici, voi... din nou, mai am o variabilă. Deci voi înlocui S 0S1. Acum am șirul - șirul rezultat 00S11, pentru că am înlocuit 0S1 cu S-ul anterior, dar 0 și 1 rămân de înainte. Ei nu merg nicăieri. Deci am, în acest moment, 00S11. Acum o să fac o altă alegere. O să-l înlocuiesc pe S-- Aș fi putut merge în orice direcție. Acest lucru ar avea ceva-- aproape ca non-determinism aici, pentru că ai de ales. O să înlocuiesc S-- în loc de 0S1, voi înlocui R, pentru că și asta este legitim din punct de vedere al regulilor. Și acum voi avea 00R11. Și acum R... nu există alegeri aici. R poate fi înlocuit doar cu un șir gol. Așa că ajung la R devine doar șir gol. Și în ceea ce privește șirul generat, șirul gol nu adaugă nimic. Pur și simplu este... este un nimic. Deci primesc șirul 0011. Și acesta este un șir doar de simboluri terminale. Și deci acesta este un șir în limba gramaticii G1. Și dacă vă gândiți bine, limbajul lui G1 este limbajul pe care l-am văzut înainte, pe care cred că l-am numit D-- 0 la k 1 la k pentru k mai mare sau egal cu 0. Deci acesta este un exemplu de limbaj ceea ce poate face o gramatică fără context, dar nu poate face un automat finit. Deci aceasta este mica noastră introducere la... hopa. Mai este un check-in aici. Oh da. Așa că vă rog să vă uitați la... lasă-mă să ies din poza asta ca să nu mă vezi blocând lucrurile. Și vom face un ultim check-in. Asigură-te că rămâi în preajmă pentru tot timpul. Acum ar putea exista mai multe dintre aceste șiruri care sunt în limbă. Trebuie să faceți clic pe toate -- toate cele pe care le-ați găsit care sunt în limba acestei gramatici care poate fi generată de gramatica G2, trebuie să faceți clic pe acelea. Îți voi acorda puțin mai mult timp pentru a vedea pe care G2 le poate genera. Îți dau un indiciu. Este mai mult de unul, dar nu toate. Așa că văd că faci ceva progres aici. Interesant. Deci, vă rog... vom încheia asta foarte repede. Poți... cineva îmi spune că nu poți dezactiva. Mulțumesc. Bine de stiut. Totuși, lucrurile vin aici. Deci haideți să nu... alergăm spre sfârșitul orei aici. Nu vreau să trec peste. Așa că o voi termina în cinci secunde. Click departe. Și nu uitați, nu vă vom taxa dacă înțelegeți greșit. Partajarea rezultatelor. Nu știu de ce are unul portocaliu acolo, pentru că aici sunt mai multe răspunsuri corecte. Deci A, B și D sunt corecte. Puteți obține oricare dintre acestea. Sunt într-adevăr un fel de două copii ale limbajului pe care îl aveam înainte unul lângă altul. Și deci singurul lucru pe care nu îl puteți obține este 1010. Așa că vă încurajez să vă gândiți la asta. Și voi ajunge la ultima noastră parte a zilei de astăzi, care este doar o scurtă trecere în revistă. Pot să mă pun înapoi. Așa că am arătat cum să convertim DFA în expresii regulate. Și rezumatul este că DFA, NFA, GNFA, chiar și expresiile regulate sunt toate echivalente în clasa de limbi pe care le pot descrie. Al doilea lucru pe care l-am făcut a fost o metodă pentru a demonstra limbajele care nu sunt obișnuite prin utilizarea lemei de pompare sau a proprietăților de închidere. Și, în sfârșit, am introdus gramaticile fără context. Și vom vedea mai multe despre acestea joi. Deci, cu asta, cred că nu mai avem timp. Și vă mulțumesc pentru notele de apreciere. Și voi... Cred că vom termina aici. Și ne vedem joi, dacă nu înainte.