MICHAEL SIPSER: Bună, oameni buni. De ce nu începem? Bine ai revenit. Mă bucur să vă văd pe toți aici. Așa că voi mai întâi... ei bine, vom recapitula ceea ce am făcut data trecută și ce vom face astăzi. Voi vorbi puțin despre setul de probleme. Și vom avea, de asemenea, o pauză, așa cum ne-am cerut, la jumătatea drumului. Așa că de ce nu sărim înăuntru? Ceea ce am făcut data trecută a fost, pe lângă introducerea cursului, am introdus automate finite în limbaje obișnuite, care sunt limbaje pe care automatele finite le pot recunoaște. Am vorbit despre aceste operațiuni regulate. Acestea ne permit să construim ceea ce numim expresiile noastre regulate. Acestea sunt moduri de a descrie limbile. Deci avem automate finite care pot descrie limbaje, iar expresiile regulate pot descrie limbaje. Și unul dintre obiectivele noastre este să arătăm că aceste două sisteme sunt echivalente unul cu celălalt, chiar dacă la prima vedere arată destul de diferit. Deci, pentru a merge în această direcție, vom demonstra proprietățile de închidere pentru clasa de limbaje obișnuite peste aceste operațiuni obișnuite. Așa că vom arăta că... ei bine, am arătat deja că oricare două limbi obișnuite au uniunea lor, fiind de asemenea obișnuite. Și vom arăta asta și pentru celelalte două operațiuni. Așa că haideți să privim înainte la ceea ce vom face astăzi. Vom introduce un concept important care va fi o temă pe tot parcursul cursului, numit nondeterminism. Și având asta ca un instrument pe care îl putem folosi, vom putea arăta închiderea sub concatenare și stea, terminând ceea ce am început să facem data trecută. Și apoi vom folosi acele construcții de închidere pentru a arăta cum să convertim expresiile regulate în automate finite. Și asta va fi la jumătatea obiectivului nostru de a arăta că cele două sisteme sunt echivalente unul cu celălalt. Și următoarea prelegere, vom arăta cum să facem conversia în cealaltă direcție. Așa că m-am gândit că vom interveni și să ne uităm la... să revenim la materialul cursului. După cum vă amintiți, ne uitam la proprietățile de închidere pentru clasa de limbi obișnuite. Am început să facem asta. Și dacă vă amintiți, sperăm, am făcut închidere sub uniune. Și apoi am încercat să facem închiderea sub concatenare, ceea ce am arătat aici pe acest slide, încercarea de dovadă pe care am încercat să o facem data trecută. Și haideți să o revizuim rapid, pentru că cred că va fi util pentru a vedea cum să remediați problema care a apărut. Deci, dacă vă amintiți, ni se oferă două limbi obișnuite, A1 și A2. Și încercăm să arătăm că și limbajul de concatenare A1A2 este obișnuit. Și așadar, modul în care procedăm cu toate aceste lucruri este să presupunem că A1 și A2 sunt regulate. Deci asta înseamnă că avem mașini, automate finite, pentru A1 și A2. Le vom numi M1 și M2, care recunosc A1 și, respectiv, A2. Și atunci ceea ce trebuie să facem pentru a arăta că concatenarea este obișnuită este să facem un automat finit care să recunoască concatenarea. Și am încercat să facem asta ultima dată. Deci, dacă vă amintiți, mașina aceea de concatenare... M, o numim... ce ar trebui să facă? Ar trebui să accepte intrarea sa dacă este în limbajul de concatenare. Și asta înseamnă că intrarea poate fi împărțită în două părți, x și y, unde x este în limba A și y este în limba B - y este acceptat de M1 - și x este acceptat de M1 și y este acceptat de M2. Îmi pare rău că am deranjat asta. Deci x ar trebui să fie în A1, iar y ar trebui să fie în A2. dacă vă puteți împărți astfel, atunci M ar trebui să o accepte. Deci M trebuie să-și dea seama dacă există vreo modalitate de a împărți intrarea, astfel încât prima mașină să accepte prima parte, a doua mașină să accepte a doua parte. Și ideea cu care am venit pentru a face asta a fost să luăm aceste două mașini, să le construim într-o nouă mașină M și apoi să conectăm stările de acceptare pentru M la starea de pornire - conectați stările de acceptare pentru M1 la început. stare pentru M2. Pentru că ideea ar fi că dacă M1 a acceptat o parte inițială, ei bine, atunci vrei să treci controlul lui M2 pentru a accepta restul. Dar după cum am observat, asta nu prea funcționează. Deoarece primul loc pentru a împărți w după ce ați găsit o parte inițială care este acceptată de M1 poate să nu fie locul potrivit. Deoarece restul poate să nu fie acceptat de M2. Poate că ai fi fost mai bine să aștepți până când ai găsit un alt loc pe care M1 l- a acceptat, mai târziu în șir, să zicem, aici. Și apoi, împărțindu-l acolo, atunci poate veți găsi cu succes că restul este acceptat de M2. În timp ce dacă ați încerca să-l împărțiți în primul rând, restul nu ar fi fost acceptat de M2. Deci tot ce trebuie să faceți... M trebuie să știe, există un loc unde să împărțiți intrarea, astfel încât să puteți obține ambele părți acceptate de mașinile respective? Problema este că M ar putea avea nevoie să cunoască viitorul pentru a ști unde să facă despărțirea. Și nu are acces la viitor. Deci ce facem? Deci, ceea ce vom face este să introducem un nou concept care ne va permite practic să obținem efectul M1-- și felul de a putea vedea viitorul. Și acel nou concept va fi foarte important pentru noi pe tot parcursul mandatului. Se numește nondeterminism. Și așa vom introduce un nou tip de automat finit numit automat finit nedeterminist. Și mai întâi, ne vom uita la asta și apoi vom vedea cum se potrivește asta cu automatul finit determinist anterior , pe care l-am introdus data trecută. Deci iată un exemplu. Este întotdeauna bine să începi cu un exemplu. Iată o imagine a unui automat finit nedeterminist . Arată foarte asemănător, la prima vedere, cu primul tip, automatul finit determinist. Dar dacă te uiți puțin cu atenție, vezi că există câteva diferențe cheie. Cea mai importantă diferență este că, în starea q1, de exemplu, în timp ce în mașinile pe care le-am introdus data trecută, trebuia să existe exact o cale de a merge pe fiecare simbol de intrare posibil, astfel încât să știi cum să urmărești mașina pe care o calculează, aici sunt două căi de mers. În q1, puteți fie să rămâneți în a1, fie să mergeți la q2. Aceasta este esența nondeterminismului. Ar putea exista multe moduri de a proceda. Și în plus, pe q1, dacă obții un b, atunci nu ai unde să mergi. Deci, acest lucru este posibil și în nondeterminism. Deci, să începem să ne uităm la aceste caracteristici. Există mai multe căi înainte - mai multe căi posibile. S- ar putea să aveți una, așa cum am avut noi înainte, sau mai multe moduri de parcurs la fiecare pas, sau poate 0 moduri de parcurs la fiecare pas. Toate acestea sunt legitime pentru o mașină nedeterministă, care face un calcul nedeterminist. O altă diferență, dacă te uiți cu atenție, este că permitem aici șirul gol să apară la o tranziție. Acest lucru este poate puțin mai puțin esențial pentru spiritul nondeterminismului. Dar se va dovedi a fi o comoditate atunci când aplicăm de fapt nondeterminismul pentru a construi mașini, așa cum veți vedea foarte curând. Acum, dacă există multe căi diferite de parcurs, și unele dintre acele căi de urmat ar putea avea rezultate diferite. După cum ne amintim de mai înainte, am acceptat intrarea, dacă ajungi într- o stare de acceptare, și am respins intrarea, dacă ajungi să nu ajungi într-o stare de acceptare, într-o stare de neacceptare. Apoi respingi. Dar acum ar putea exista mai multe moduri diferite de a merge. Și vom face un exemplu într-un minut. Dar ar putea exista mai multe moduri diferite de a merge. Și s-ar putea să nu fie de acord. Unii dintre ei ar putea accepta. Alții ar putea să respingă. Atunci ce faci? Ei bine, în acest caz, acceptarea anulează întotdeauna respingerea. Aceasta este esența nondeterminismului în felul în care îl stabilim. Puteți întreba de ce este asta. Iar spiritul acestui lucru va deveni clar la momentul potrivit. Dar acum, luați-o ca o regulă. Când avem o mașină nedeterministă, acceptarea anulează respingerea. Deci, atâta timp cât există... una dintre căile posibile de urmat ajunge la o acceptare, spunem că totul este acceptat. Singurul mod în care putem respinge -- dacă toate căile posibile de a merge ajung la respingere, ajung într-o stare de non-acceptare. Așa că vom vedea un exemplu de... Cred că vom face un exemplu chiar acum, da. Deci, dacă luăm, de exemplu, această mașină N1 acum pe o intrare ab-- și vom procesa simbolurile unul câte unul, la fel cum am făcut înainte. Dar acum, pentru a urma, ar putea exista mai multe căi diferite de urmat. Deci, dacă luăm primul simbol a și rulăm mașina-- atunci când mașina, pornește în starea stea, ca înainte-- dar acum apare un a. Și ar putea fi două-- acum sunt două moduri diferite de a merge. Așa că le vom urmări pe amândoi. După ce aparatul citește un a, vă puteți gândi la acesta ca fiind în două stări acum simultan. Poate fi în starea q1 și poate fi în starea q2. Deci acestea sunt două locuri posibile diferite în care ar putea fi în acest moment. BINE? Acum citim următorul simbol, b. Și de la a b, luați fiecare dintre locurile în care ar putea fi mașina la sfârșitul simbolului anterior și apoi aplicați citirea a b, următorul simbol, din fiecare dintre acele stări în care ar putea fi mașina de la simbolul anterior. Deci mașina ar putea fi în q1 și q2 după ce a citit un a. Acum aplicăm un b. Ei bine, q1 pe a b nu merge nicăieri. Deci te gândești la acea ramură, dacă vrei, a calculului ca pe moarte. Nu are încotro. Pur și simplu dispare. Cu toate acestea , cealaltă posibilitate, care a fost starea q2 pe a b, permite, are un loc. Deci mașina va trece acum de la q2 la q3 pe acea ramură a calculului, care citire-- la citirea a b. Și apoi are, ieșind din q3, există două simboluri. Există un simbol a și un șir gol. Acum, pe un a, mașina ar trebui să citească un a pentru a trece de-a lungul acelei săgeți. Dar când există un simbol gol pe săgeată, asta înseamnă că mașina poate merge de-a lungul acelei săgeți gratuit, fără măcar să citească nimic. Atâta timp cât ajunge la q3, poate sări automat q4. Și astfel, odată ce a citit un b și a trecut la q3, acum poate fie să rămână în q3, fie poate merge de-a lungul tranziției goale și să meargă la q4. Deci, din nou, va fi un pas nedeterminist în acest moment. Esența unei tranziții goale este că va exista nondeterminism. De aceea nu am introdus asta pentru automatele deterministe, pentru că nu trebuie să faceți tranziția de-a lungul unei tranziții de șir goale. Puteți rămâne acolo unde sunteți sau puteți merge de-a lungul tranziției șirurilor goale fără a citi nicio intrare și treceți la următoarea stare, care, în acest caz, este q4. Deci haideți să vedem unde suntem. După citirea unui a, suntem în stările q1, q2. Dar acum, după ce citim a b, suntem în stările q3 și q4 ca posibilități. Și acum suntem la sfârșitul introducerii și ne uităm și vedem ce avem. Dacă vreuna dintre stări ca posibilități în care ne aflăm chiar acum la sfârșitul șirului este o stare de acceptare, atunci spunem, în general, mașina a acceptat. Deci, asta corespunde cu ceea ce am spus aici înainte - acceptați intrarea dacă o cale duce la o acceptare. Deci, dacă vreun mod de a proceda prin aceste alegeri nedeterministe vă va conduce la o acceptare, atunci veți spune, vom accepta intrarea. BINE? Deci această intrare aici este acceptată. Să facem un alt exemplu. Să presupunem că avem intrarea aa în loc de ab. Deci aa, după prima zi, ca și înainte, suntem în stările q1 și q2 ca posibilități. Acum citim din nou un a. Acum, cea care este în starea q1, acea posibilitate, posibilitatea q1, după ce a citit un a, se ramifică din nou la q1 și q2. Deci, știm că după citirea celui de-al doilea a, vom fi în cel puțin q1 și q2. Acum, ce zici de starea care fusese pe q2 la citirea unui a, cea de înainte? După ce ai citit primul a, ai fost în q2. Acum citind a doua a, nu ai unde să mergi. Deci, acela este doar eliminat. Deci, după citirea aa, rămânem în stările q1 și q2 ca posibilități. Niciuna dintre acestea nu este state acceptate. Prin urmare, la intrarea aa, mașina respinge. BINE? Hai să mai facem câteva, apoi îți voi cere să faci una. Deci avem aba ca intrare. Să vedem ce se întâmplă atunci. Deci, amintiți-vă, după ce ați citit ab, mașina este în cele două stări q3, q4 ca posibilități. Asta avem din primul exemplu. Deci, după ce am citit ab, suntem în stările q3, q4. Acum citim un alt a. Q4 de pe un a nu are încotro. De fapt, nu are unde să meargă în nicio intrare. Deci, indiferent de ce apare după ce ești în starea q4, ramura aceea moare. Dar pe q3, care este o altă posibilitate de citire a unui a, poate urma doar o tranziție. Pentru că aceasta este una dintre etichetele acelei tranziții, este a. Deci, puteți urma doar în tranziție citirea unui a, care este ultimul simbol din șir. Și așa că acum, după aba, ești doar în starea q4 ca posibilitate. Dar se întâmplă să fie o stare de acceptare, așa că mașina acceptă. BINE. Și acum, în sfârșit, să luăm exemplul nostru final. Ce se întâmplă dacă avem abb? Deci, după cum ne amintim mai devreme, după ce am citit ab-- acesta a fost primul exemplu-- eram în stările q3, q4 ca posibilități. Acum citim un b. Ei bine, niciunul dintre acele state nu are unde să meargă pe un b. Deci acum toate firele, toate ramurile, ale calculului mor. Și în acest moment, mașina este complet moartă. Nu mai are posibilități active. Deci, cu siguranță, va respinge această intrare, deoarece niciuna dintre stările active -- nu există stări active sau stări de acceptare. Și, de fapt, dacă te uiți la orice a venit mai târziu, orice ar fi extins șirul abb ar fi de asemenea respins. Pentru că odată ce mașina a avut toate... toate posibilitățile au dispărut, nu există nicio modalitate de a reveni la viață cu nicio extensie. Deci, cu asta... oh, iată un punct important înainte de a trece la un check-in pentru tine. Dar cred că un lucru care ar putea fi în mintea ta despre acest nondeterminism este cum corespunde asta cu realitatea? Ei bine, nu este. Nu intenționăm nondeterminism, deoarece îl definim pentru a corespunde unui dispozitiv fizic. Dar, cu toate acestea, după cum veți vedea, este un concept foarte util din punct de vedere matematic , acest nondeterminism. Și va juca un rol important pe parcursul subiectului, așa cum îl vom experimenta în restul trimestrului. Deci, cu asta, o să fac un mic check-in. Vă voi cere să luați în considerare ce se întâmplă pe una dintre intrări. Deci iată-ne. Ce face la intrarea aab? Deci iată mașina. Poți să te uiți la el. Și să presupunem, să sperăm, că există un sondaj aici pe care să-l dau pentru tine, ca să- mi poți da părerea ta. Deci, ce face aparatul la intrarea aab? Cei mai multi dintre voi ati raspuns. Din nou, nu veți fi penalizat pentru răspunsul greșit. Dar sperăm că vei primi răspunsul corect. Oricum, hai să aruncăm o privire aici. Deci timpul a trecut. Să încheiem sondajul și să împărtășim rezultatele. Deci majoritatea dintre voi, majoritatea ați primit răspunsul corect, care este a. Aparatul acceptă aab. Pentru că atunci când ai o... așa că îți voi arăta calea care corespunde acceptării. Mergi a, a, b și apoi șir gol. Și astfel acea secvență de pași este una dintre posibilitățile nedeterministe pe care le poate urma mașina. Și asta arată că aparatul acceptă intrarea aab. Vă puteți gândi la asta, așa cum am făcut-o și înainte. Dacă citiți un a, este în cele două posibilități q1, q2. Citiți o secundă a, din nou, în posibilitățile q1, q2. Acum ai citit un b. Este în posibilitățile q3, q4. Și asta e tot, aab. Deci acum ai citit b. Este în posibilitatea q3, q4. q4 este o stare de acceptare. Asta anulează starea de neacceptare. Și așa mașina acceptă. Trebuie să înțelegi asta. Deci, dacă nu ați înțeles bine, întoarceți-vă și gândiți-vă unde ați alunecat. BINE? Pentru că asta abia începe... ne încălzăm aici. Va deveni mult mai greu. OK, așa că nu mai împărtășiți rezultatele. Și deci hai să continuăm. Deci, așa cum am făcut data trecută, putem defini formal un automat finit nedeterminist. Iată din nou poza. BINE. Deci seamănă mult cu cazul pe care l-am avut înainte, Automatele finite deterministe sau DFA, așa cum le vom numi. Este un tuplu de 5. Așa că am notat mici mementouri pentru care sunt acele componente ale acelui tuplu de 5 , acea listă de cinci componente. Deci sunt toate la fel ca înainte -- stări, alfabet, funcție de tranziție, stare de pornire și stări de acceptare. Astfel încât definiția formală să arate exact aceeași, cu excepția structurii funcției de tranziție. Așa că acum, înainte, dacă îți amintești, aveai o stare și un simbol de intrare și ai revenit la o stare. Acum avem ceva mai complicat. Avem o stare și un simbol de intrare, dar în loc de doar sigma, este sigma sub epsilon. Și asta este o prescurtare pentru sigma union epsilon. Și acesta este o modalitate - felul meu de a spune că aveți voie să aveți pe săgețile de tranziție fie un simbol de intrare, fie un șir gol. Deci, funcția de tranziție trebuie să vă spună ce să faceți când apare și un șir gol. Deci asta ar face parte din tabelul tău pentru funcția de tranziție. Acum, aici, ce se întâmplă aici? Ei bine, acum, în loc să produci doar o singură stare, când ai citit, de exemplu, un a din q1, există un întreg set de posibilități. Deci aici avem ceea ce se numește un set de putere. Acesta este setul de submulțimi ale colecției Q. Deci aici vom produce un întreg subset de stări. În loc să iasă doar o singură stare, ar putea exista un subset de stări posibile la care poți merge. Deci, setul de putere al lui Q este un set de submulțimi ale lui Q. Deci asta înseamnă această notație. Din nou, acesta este ceva pe care , sper, vi-l prezint ca un pic de memento. Ai mai văzut asta în altă parte. Dar vă rugăm să vă asigurați că înțelegeți notația, în continuare, pentru că vom face mai puține ține de mână pe măsură ce începem să mergem înainte. BINE. Deci haideți să aruncăm o privire. În exemplul N1 de aici, doar pentru a ilustra ce se întâmplă, când sunteți în starea q1 citind un a, acum obțineți un set întreg de posibilități, care, în acest caz, este q1 și q2. În timp ce, dacă citești un b, care ar fi acel set? Din q1, care este setul de posibile stări succesoare? Ei bine, nu există. Deci este setul gol. BINE? Deci, sperăm că înțelegeți notația de aici. Deci acum iată, cred, cu adevărat important. Cum înțelegem nondeterminismul, intuitiv vorbind? Și există mai multe moduri diferite, care fiecare își are valoarea în circumstanțe diferite. Deci, o modalitate este să ne gândim la nondeterminism ca pe un fel de paralelism. Deci, de fiecare dată când mașina are de făcut o alegere nedeterministă , în cazul în care există mai multe rezultate, te gândești la mașină ca la o ramificare, bifurcare, noi fire ale calculului paralel în acea etapă, în care își face o copie întreagă a ei atunci când există o alegere de posibilități. Și apoi fiecare dintre aceștia procedează în mod independent să citească restul intrării ca fire separate ale calculului. Deci, dacă sunteți familiarizat cu calculul paralel, acest lucru ar trebui să vă fie destul de familiar. Singurul lucru cheie de reținut este că, deoarece acest lucru oferă o serie de posibilități, regula de acceptare este că, dacă oricare dintre aceste posibilități ajunge la o acceptare la sfârșitul introducerii, se ridică un steag și spune, acceptă. Și asta îi depășește pe toți ceilalți. Deci acceptarea domină. Deci, un alt mod de a-l privi este perspectiva matematică, unde vă puteți imagina - și vom folosi toate acestea. Deci chiar trebuie să le înțelegeți pe toate. Viziunea matematică este că te poți gândi la calcul ca la un fel de arbore de posibilități. Deci, începeți de la început, de la rădăcina calculului, atunci când începe cu adevărat. Dar de fiecare dată când are loc o ramificare nedeterministă , acel nod al arborelui are mai mulți copii care ies din acel nod. Și astfel, diferitele fire ale calculului corespund diferitelor ramuri ale acelui arbore. Și acum vei accepta dacă vreuna dintre acele ramuri duce la o stare de acceptare... OK, evident, oarecum similar cu ceea ce aveam înainte. Dar cred că este puțin o perspectivă diferită asupra modului în care să ne gândim la nondeterminism. Și ultimul va suna puțin ciudat. Dar, de fapt, cred că pentru oamenii care sunt în afaceri, este cel pe care îl folosesc cel mai mult. Și acesta este modul magic de a gândi nondeterminism. Și adică, atunci când mașina are de făcut alegeri nedeterministe, te gândești la mașină ca ghicind-o pe cea corectă în fiecare etapă, iar cea corectă este cea care o va determina în cele din urmă să o accepte. BINE? Deci, vă puteți gândi la mașină ca ghicind care este calea corectă de urmat. Și dacă există o cale corectă de urmat, întotdeauna se ghicește corect. Desigur, dacă mașina ajunge să respingă, pentru că nu există o cale corectă de urmat, atunci nu contează. Nu există nicio presupunere bună. Dar dacă există o presupunere bună, ne vom gândi la mașină ca și cum preia acea presupunere bună și merge în acest sens. BINE. Deci acum iată un lucru foarte important. Am introdus acest nou model, Automatul finit nondeterminist , NFA. Se pare că , deși pare mai puternic, pentru că are acest nondeterminism, nu este mai puternic. Poate face exact aceeași clasă de limbi, limbile obișnuite. Și vom arăta că cu această teoremă aici, dacă un NFA recunoaște a, atunci a este regulat. Așadar, vom demonstra acest lucru, arătând cum să convertiți un NFA într-un DFA echivalent, care folosește aceeași limbă. Deci putem lua un NFA care are nondeterminism și găsim un alt DFA care nu are nondeterminism, dar folosește același limbaj. Acceptă exact aceeași putere, chiar dacă îi lipsește această capacitate nedeterministă. Acest lucru va fi extrem de util, apropo, și, de exemplu, pentru a arăta acea închidere sub concatenare. OK, așa că în această prezentare aici, voi ignora tranzițiile epsilon. Pentru că, odată ce ți-ai dat ideea cum să faci asta, ai putea să-ți dai seama cum să le încorporezi. Ei doar fac lucrurile puțin mai complicate. Deci, să ne concentrăm doar pe aspectul cheie al nondeterminismului, și anume că mașina ar putea avea mai multe căi de parcurs în orice moment. Ar putea exista mai multe stări următoare pe o intrare. BINE? Acum ideea construcției -- așa că vom începe cu o mașină nedeterministă M și vom construi o mașină deterministă M prim, care face exact același lucru. Și modul în care funcționează M prime este că va face ceea ce ai face dacă ai simula M. Ce ai face? Aceasta este ceea ce făceam în timp ce v-am explicat. Dacă simulați M, de fiecare dată când obțineți un simbol de intrare, trebuie doar să urmăriți care este setul de stări posibile în acel moment. Asta va face DFA. va trebui să țină evidența în ce posibil set de state s- ar putea afla NFA în punctul de intrare în care ne aflăm acum. Și apoi, pe măsură ce ajungeți la următorul simbol, DFA va trebui să actualizeze lucrurile pentru a ține evidența următorului set de stări în care s- ar putea afla NFA în acest moment, la fel cum ați face dumneavoastră. BINE? Și iată un fel de imagine. Și cum implementăm asta? Deci, aici este NFA cu care începem, M, și vom face aici DFA. Dar pentru a ne aminti în ce set de stări ar putea fi DFA la un moment dat, deci poate că este în setul de stări în care ar putea fi M. Am spus greșit? Ce set de stări ar putea fi NFA într-un timp dat -- deci poate M, NFA, ar putea fi, la un moment dat, în starea q3 și q7. Modul în care DFA ține evidența asta, va avea o stare pentru fiecare subset posibil de stări ale NFA. Așa își amintește în ce subset de state se află NFA. Acesta este modul în care funcționează DFA-urile. Au o stare separată pentru fiecare posibilitate pe care trebuie să o urmărească. Și posibilitățile aici sunt diferitele subseturi de state în care s-ar putea afla NFA la un moment dat. BINE? Deci, corespunzător acestui submult, acestor două posibilități q3, q7, DFA va avea o stare cu submulțimea q3, q7. Și va fi, pentru fiecare submulțime posibilă aici, va exista o stare diferită a lui M prim. Deci M prim va fi mai mare. BINE. Atât de repede, construcția lui M, stările lui M prim acum, q prim, vor fi mulțimea de puteri, mulțimea de submulțimi de stări din mașina originală M. Și acum trebuie să ne uităm la modul în care funcția de tranziție a lui DFA, când ați făcut mașinile amorsate ale DFA, mașina DFA. Deci acestea sunt componentele deterministe. Deci delta prim, atunci când are un subset, ceva de genul acesta, are una dintre stările sale, care corespunde unui subset de stări ale lui M și citește un simbol de intrare, trebuie doar să faceți actualizarea așa cum ați face-o în mod natural . O să te uiți la fiecare stare din R, să te uiți la unde poate ajunge sub a-- așa că există o grămadă de seturi acolo. Și uitați-vă la toate stările posibile care ar putea fi într-unul dintre acele subseturi și acesta este setul de stări pe care ați putea fi. Acesta va fi noul set de stări și acesta va fi în noua stare a lui M prim. BINE? Deci, va fi submulțimea corespunzătoare tuturor stărilor care ar putea fi în, atunci când aplicați funcția de tranziție a mașinii nedeterministe, la una dintre stările din submulțimea stărilor în care ar putea fi mașina nedeterministă. OK? Este un pic de gură. Îți sugerez să te uiți la asta, dacă nu ai înțeles prea bine , după fapt. Bine de înțeles. Etapa de pornire pentru NFA-- pentru DFA-- Îmi pare rău-- va fi subsetul cu care vom începe acum. Va fi submulțimea corespunzătoare doar stării de început a lui M. Și stările de acceptare vor fi-- ale mașinii deterministe vor fi toate submulțimile care au cel puțin o stare de acceptare din NFA. BINE? Așa că sper că ai înțeles asta. Pentru că o să-ți mai fac un mic check-in aici. Care este să te întreb, cât de mare este M prim? Câte stări are M prim? Ți-am spus care sunt acele state. Deci, gândește-te la asta. Deci, verificați două -- dacă M are n stări, câte stări are M prim prin această construcție? OK, deci hai să lansăm următorul sondaj. OK, cinci secunde... și cred că aproape am terminat. bun. Bine, împărtășește rezultatele... Nu știu dacă partajarea rezultatelor este un lucru bun. Nu încerc să te fac, dacă nu ai primit răspunsul corect -- pentru că majoritatea oamenilor au primit răspunsul corect -- dar dacă nu ai primit răspunsul corect, încerc să te fac să te simți rău. Dar este o mică sugestie că trebuie să revizuiți câteva concepte de bază. Deci, conceptul de bază aici este dacă aveți o colecție - aveți un set de stări, câte subseturi există? Și numărul de submulțimi va fi exponențial. Deci, dacă aveți o colecție de n elemente, numărul de submulțimi ale acelor n elemente este de la 2 la n. Acesta este faptul pe care îl folosim aici. Și de aceea M prim are 2 la n stări, dacă M ar avea n stări. Și ar trebui să te asiguri că înțelegi de ce. Bine, așa că cu asta, așa cum a fost cerut, vom avea o mică pauză. Și acea pauză ne va dura exact cinci minute. Așa că ne vom întoarce în cinci minute. Voi fi prompt. Așa că ți-am dat un mic cronometru aici. Așa că te rog, o voi începe chiar când se termină. OK, aproape gata. Sper că sunteți cu toții împrospătați și pregătiți pentru a doua jumătate. Deci, acum că avem nondeterminism, vom folosi asta ca un instrument pentru a demonstra proprietățile de închidere pe care ne-am propus, începând de la ultima prelegere. BINE. Deci, amintiți-vă, să ne uităm la închiderea sub un sindicat. Acum, am făcut asta deja, dar o voi face din nou, dar de data aceasta, folosind nondeterminism. Și vei vedea cât de puternic este nondeterminismul. Pentru că ne va permite să o facem aproape fără efort. Vom începe așa cum am făcut înainte. Voi începe cu două DFA. Dar, de fapt, acestea ar putea fi chiar și NFA. Dar să presupunem că am început cu cele două DFA pentru cele două limbi A1 și A2. Și acum vom construi un NFA, care să recunoască uniunea. Și asta este suficient de bun, pentru că știm deja că putem converti NFA în DFA. Și, prin urmare, ei fac și limbi obișnuite. BINE. Așadar, acum, iată cele două DFA care folosesc limbile A1 și A2. Și ceea ce voi face este să le adun într-o pungă de state, care va fi M, NFA care va face limbajul uniunii. Deci, amintește-ți... ce ar trebui să facă M? M ar trebui să accepte intrarea sa, dacă M1 sau M2 acceptă. Deci cum va face asta? Ce va face, vom adăuga o nouă stare la M, care se va ramifica sub tranziții epsilon. Și acum puteți începe să vedeți cât de utile ne vor fi aceste tranziții epsilon. Trecerea la ramificare sub tranziții epsilon la cele două stări inițiale de început ale M1 și M2. Și am terminat. De ce? Ei bine, acum, nedeterminist, pe măsură ce primim o intrare, w vine în M-- și la început, chiar și imediat după ce începe, primul lucru care se întâmplă este că se va ramifica în M1 și, de asemenea, va ramifica în M1. M2 nedeterminist ca două posibilități. Și apoi în M1 și M2, va începe de fapt să citească intrarea. Și fiecare va urma acum, așa cum ar avea inițial stările corespunzătoare citirii acelor simboluri de intrare. Și M, ca o combinație de M1 și M2, va avea o posibilitate pentru o stare în M1 și o stare în M2. Și astfel, M le va avea combinate într-un singur pachet. Și acum, la sfârșitul intrării, dacă oricare dintre acestea ajunge într-o stare de acceptare, atunci M va accepta ca un automat finit nedeterminist . Pentru că așa funcționează nondeterminismul. Acceptați dacă oricare dintre filiale a ajuns să accepte, ceea ce este exact ceea ce aveți nevoie pentru unire. Deci, când facem unire, vrei ca oricare dintre acestea să accepte. Iar nondeterminismul este construit convenabil pentru a ne permite să facem unirea aproape gratuit. Deci, puteți din nou, gândindu-vă la nondeterminism ca termeni ai paralelismului, vă puteți gândi la mașina nedeterministă ca rulând în paralel M1 și M2 pe intrare. Și dacă unul dintre ei ajunge să accepte, M va accepta. Sau vă puteți gândi la asta în termenii acelei presupuneri la care m-am referit mai devreme, ceea ce înseamnă că, pe măsură ce M devine -- când tocmai este pe cale să citească primele simboluri ale intrării sale, ghicește dacă aceasta va fi o intrare acceptată de M1 sau o intrare acceptată de M2. Iar magia nondeterminismului este că ghicesește întotdeauna corect. Deci intrarea se întâmplă să fie o intrare care va fi acceptată de M2. M va ghici că M2 este calea corectă de urmat. Și va merge pe direcția M2. Deoarece nondeterminism, magia este întotdeauna ghiciți corect. Mi-aș dori să fie adevărat în viața reală. Ar face examenele mult mai ușor. Oricum, acum să vedem cum putem folosi asta pentru a face închiderea sub concatenare. OK, așa că acum vom avea de fapt o imagine foarte asemănătoare cu cea pe care o aveam inițial. Dar acum folosind nondeterminism, îl putem face să funcționeze. Deci aici avem cele două mașini care fac cele două limbi, A1 și A2. Și le vom combina într-o mașină mai mare M, așa cum se arată. Amintiți-vă, ceea ce ar trebui să facă M este să își accepte intrarea, dacă există vreo modalitate de a împărți acea intrare, astfel încât prima jumătate să fie acceptată de M1, iar a doua parte să fie acceptată de M2. Modul în care vom obține acest efect este prin introducerea unui tranzit gol -- tranziții goale, tranziții epsilon, trecând de la stările de acceptare a lui M1 la starea de început a lui M2, așa cum am arătat în această diagramă. Deci acestea au fost stările originale de acceptare ale lui M1. Și acum vor fi declasificate ca state acceptante. Dar vor avea noi tranziții, tranziții goale, atașate lor, care le vor permite să se ramifice la M2 fără a citi nicio intrare. Și intuitiv vorbind, acest lucru va face ceea ce trebuie. Deoarece odată ce M1 a acceptat o parte din w, atunci puteți ramifica nedeterminist la M2. Și veți începe procesarea în M2. Iar ideea este -- am sărit înaintea mea -- este că motivul pentru care rezolvă problema pe care o aveam înainte este că tranzițiile epsilon nu-- mașina nu trebuie să accepte asta. Poate rămâne acolo unde este ca o opțiune nedeterministă sau se poate deplasa de-a lungul tranziției epsilon, fără a citi nicio intrare, ca o altă opțiune nedeterministă. Deci folosește acest nondeterminism acum pentru a rămâne în M1 pentru a continua să citești mai mult din intrare și pentru a sări în M2 pentru a începe procesarea ceea ce ar putea fi a doua jumătate sau a doua parte a intrării pe care M2 o acceptă. Și vă puteți gândi la asta în termeni de ghicire, ca și cum mașina ghiceste unde să facă acea împărțire. Odată ce a găsit o parte inițială care este acceptată de M1, ghicește că acesta este punctul de împărțire corect. Și asta trece la M2. Dar ar putea exista și alte presupuneri pe care le-ar putea face corespunzătoare altor posibilități. Și așa în cazul nondeterminismului, întotdeauna ghicește corect. Dacă există o modalitate de a împărți șirul în două părți acceptate de M1 și M2, mașina va face acea ghicire bună. Și apoi M1 va accepta prima parte, iar M2 va accepta cu a doua parte. Și îl vom face pe M să accepte întregul șir. Și aceasta este soluția puzzle-ului nostru despre cum facem închiderea sub concatenare. OK, sper că a trecut. Pentru că doar începem cu nondeterminism. Vom folosi mult nondeterminismul și va trebui să te simți foarte confortabil cu el. BINE? Acum să facem închiderea sub stea. Și închiderea sub stea funcționează foarte similar, dar acum vom avea doar o singură limbă. Dacă A este regulată, la fel este și A steaua. Deci nu sunt o pereche de limbi, pentru că o stea este o operație unară care se aplică doar unei singure limbi. Deci, dacă avem un DFA care recunoaște A, pentru a arăta că O stea este obișnuită, trebuie să construim o mașină care să recunoască A. Și mașina pe care o vom construi este ca înainte și apoi un NFA. BINE? Deci iată M, DFA pentru A. Și vom construi un NFA M prim care recunoaște stea A. Și să ne gândim acum, ce înseamnă să recunoști O stea? Deci, dacă o să vă dau o contribuție, când este în limba vedetă? Ce trebuie să facă M prime? Deci, amintiți-vă ce este steaua. Steaua înseamnă că poți lua câte copii dorești din șiruri în limba originală, și asta în limba stea. Deci, pentru a determina dacă ceva este în limba vedetă, trebuie să vedeți, pot să îl despart în bucăți care sunt toate în limba originală? Așa că vrei să vezi, pot să iau contribuția mea w și să o tai în câteva bucăți -- patru, în acest caz -- în care fiecare dintre acele piese sunt membri ai lui A, membrii limbii originale? Deci asta este treaba lui M prime. Are intrarea sa și vrea să știe, pot tăia acea intrare în bucăți, fiecare dintre acestea fiind acceptată de mașina originală M? Asta face M prime. Și dacă te gândești puțin la asta, într-adevăr, ceea ce se întâmplă este că de îndată ce M-- deci M prime va simula M. Așa îmi place să mă gândesc la asta, ca având M înăuntru. Deci, dacă urma să faci asta singur, vei lua w. Îl vei rula o vreme. Vei vedea, oh, M este acceptat. Acum trebuie să-l reiau să văd dacă acceptă următorul segment. Deci, de fiecare dată când M acceptă, veți reporni M pentru a vedea dacă acceptă alt segment. Și astfel, făcând asta, vei tăia w în diferite segmente, fiecare dintre acestea fiind acceptată de M. Desigur, nu este niciodată complet clar dacă ar trebui, pentru un anumit segment, să- l tai acolo sau ar trebui să mai aștepte puțin și să găsească altul, un loc mai târziu pentru a tăia. Dar aceasta este exact aceeași problemă pe care am avut-o înainte cu concatenarea. Și am rezolvat-o folosind nondeterminism și o vom rezolva din nou folosind nondeterminism. Deci, modul în care vom obține acel efect de pornire din nou a mașinii, odată ce este acceptat, este prin adăugarea de tranziții epsilon care merg de la stările de pornire înapoi la-- de la starea de acceptare înapoi la starea de pornire. Deci, acum, de fiecare dată când M a acceptat, are o opțiune, nu o cerință, dar are o opțiune. Fie poate continua procesarea, fie poate reporni, făcând o tăietură în acel moment și încercând să vadă dacă mai există un al doilea, un alt segment al intrării pe care îl va accepta. Și asta este, practic, totul, cu o mică problemă cu care trebuie să ne confruntăm. Și asta este, trebuie să ne asigurăm că M prim acceptă șirul gol. Pentru că amintiți-vă, șirul gol este întotdeauna un membru al limbajului stele. Și așa cum este scris chiar acum, vom cere să existe cel puțin o copie a cel puțin unui segment. Nu luăm în considerare posibilitatea lipsei segmentelor, care este șirul gol. Și modul în care vom obține asta este... ei bine, vreau să spun, un lucru, o modalitate de a ajunge să adăugăm... așa că ne lipsește șirul gol chiar acum. Deci cum o reparăm? Practic, vom lua doar construcția pe care o avem pe ecran și o vom ajusta pentru a adăuga șirul gol. Pentru că este posibil să lipsească. O modalitate de a face asta, care este tentant, dar greșit, este de a face din starea de început a lui M o stare de acceptare pentru M prim. Așa că am fi putut face și din asta o stare de acceptare. Și acum M prim va accepta, de asemenea, șirul gol. Asta e vestea bună. Problema este că data de începere ar putea juca un alt rol în M, în afară de faptul că este doar începutul. Pot exista momente când M revine la starea de pornire mai târziu. Și dacă facem din starea de început starea de acceptare, va începe brusc să accepte și o grămadă de alte lucruri, care ar putea să nu fie intenționate. Așa că este o idee proastă să faci din starea de început o stare de acceptare. În schimb, vom lua soluția simplă alternativă de a adăuga o nouă stare de pornire, la care nu va fi niciodată revenită sub nicio circumstanță, și vom face din aceasta un nou început -- o stare de acceptare, de asemenea. Deci aici, va trebui să facem această modificare suplimentară. Deci, așa cum spun, asta este ceea ce trebuie să facem. Și modul în care vom face asta este prin adăugarea unei noi stări de pornire, care este și o stare de acceptare, pentru a ne asigura că acceptă șirul gol. Și apoi și asta se poate ramifica pentru a începe M ca înainte, dacă șirul care este introdus nu este șirul gol. Și atunci M prime va trebui de fapt să lucreze pentru a vedea dacă poate fi întrerupt, așa cum făcea înainte. Deci asta este dovada închiderii sub stea. Nu voi face nimic dincolo de ceea ce tocmai am descris. Aceste dovezi prin imagine sunt destul de convingătoare, sper. Și dacă nu, ele sunt explicate ceva mai detaliat, ceva mai formal, în manual. Dar pentru prelegere, aici mă voi opri, cu aceste două argumente. Și acum... oh, avem o verificare rapidă despre asta. Deci dacă M are n stări, câte stări are M prim prin această construcție? Deci nu intenționez ca acestea să fie foarte grele, mai mult doar să te țin treaz. Deci câte stări are M prim? OK, poate puțin prea ușor chiar și pentru un check-in. Da, toată lumea primește asta. Pentru că tot ce ai făcut a fost... am adăugat un nou stat. Deci răspunsul este așa cum ai tu... Cred că aproape toată lumea observă că este numărul b. Așa că voi încheia sondajul și voi împărtăși rezultatele. Și toată lumea l-a primit pe acela. Și deci hai să continuăm. Și, deci, ultimul lucru pe care îl vom face astăzi este să vă arătăm cum să convertiți expresiile regulate în NFA, arătând astfel că fiecare limbă pe care o puteți descrie cu o expresie regulată este un limbaj obișnuit. Marți, vom arăta cum să faceți conversia în cealaltă direcție și, prin urmare, vom arăta că aceste două metode de descriere a limbilor sunt echivalente una cu cealaltă. Deci iată teorema noastră. Dacă R este o expresie regulată, iar A este limbajul - un set de șiruri de caractere descrise de acea expresie regulată , atunci A este regulat. BINE? Așa că vom arăta cum să conversii. Strategia este de a converti R într-un NFA M echivalent. Așa că trebuie să ne gândim, amintiți-vă, la aceste expresii regulate pe care le-am introdus data trecută. Acestea sunt aceste expresii care arată ca ab union b star, ceva de genul asta-- atât de construite din operațiile obișnuite din expresiile regulate primitive care nu au nicio operație, pe care le numim atomice. Deci, dacă R este o expresie regulată atomică, arată ca fie doar un singur simbol, fie un simbol șir gol sau un simbol de limbaj gol. Sau R poate fi o expresie regulată compusă -- ui. Avem puțin... da, așa că avem două posibilități aici. R este fie atomic, fie compozit. Și deci să ne uităm la care este expresia echivalentă în fiecare caz. Deci, dacă R este doar expresia regulată cu o singură literă, aceasta este o expresie regulată total legitimă, doar o expresie regulată 1. Deci, aceasta descrie doar limbajul șirului 1. Deci trebuie să facem un NFA care acceptă - care recunoaște doar acel limbaj, acceptă doar șirul 1. Deci este un NFA foarte simplu. Doar începe în starea de pornire. Și pe acel simbol unic, se ramifică într-o stare de acceptare. Și nu erau permise alte tranziții. Așa că dacă mai primești ceva în afară de acel șir, care este doar acel simbol, NFA îl va respinge. Dacă este prea lung, dacă vine aa, ei bine, nu există unde să pleci din această stare de acceptare pe un A. Deci mașina va muri. Trebuie să fie într-o stare de acceptare la sfârșitul intrării. Acum, vreau să vă gândiți singuri pentru un minut, cum facem un NFA care acceptă doar șirul gol și nu alte șiruri? Puteți face asta cu un singur stat cu un NFA, doar acesta aici. Mașina va porni în starea de pornire, care este, de asemenea, imediat o stare de acceptare. Deci acceptă șirul gol. Dar dacă mai intră ceva, nu ai unde să mergi când mașina moare. Deci această mașină acceptă doar șirul gol. Sau limba sa este limba cu un element, șirul gol. Ce zici de limba goală? Ei bine, aici este un NFA care nu are nicio stare de acceptare, deci nu poate accepta nimic. Acum, dacă avem o expresie regulată compusă, am terminat deja. Pentru că am arătat cum să construim... am arătat construcții care ne oferă închidere sub unire, concatenare și stea. Și acele construcții ne vor permite să construim NFA-uri care fac limbajul acestor expresii regulate mai complexe construite din NFA-uri care fac părțile individuale. Deci, dacă avem deja NFA care fac R1 și R2, atunci închiderea în construcție unională ne oferă o NFA care face R1 uniunea R2 ca limbaj. Așa că sper că este clar, dar voi face un exemplu care sper să îl ilustreze. Și vă va arăta-- practic, ceea ce vă ofer este o procedură automată pentru conversia unei expresii regulate într-un NFA echivalent. Așa că haideți să vedem acea procedură în acțiune, care de fapt urmează doar această rețetă pe care v-am descris-o. Deci aici este o expresie regulată a union ab star. Deci aceasta este o expresie regulată. Este un limbaj. Orice ar fi, nu-mi pasă. Dar vreau să fac un NFA care să recunoască aceeași limbă. Și felul în care voi face asta este mai întâi să construiesc NFA pentru componente, subexpresiile acestei expresii regulate și apoi să le combin, folosind instrucțiunile noastre de închidere , pentru a fi NFA pentru subexpresii din ce în ce mai mari, până când obțin NFA care este echivalentul întregii expresii. Deci hai să vedem cum merge. Deci, cele mai primitive părți, cele mai mici subexpresii de aici, sunt doar expresiile pentru a și pentru b. Deci iată-l doar pentru a. Deci acesta este NFA care recunoaște limbajul, care este doar un șir a. Aici este NFA al cărui limbaj este doar un șir b. Și acum vreau un NFA care acceptă doar șirul ab. Acum, desigur, ai putea să faci asta de mână. Este destul de simplu. Dar ceea ce susțin este că putem face acest lucru automat, folosind construcția de închidere pentru concatenare. Pentru că într-adevăr există un simbol de concatenare ascuns. Acesta este un concatenat b. Așa că acum pentru ab, voi lua lucrul de la a și partea din b-- deci aceste două lucruri pe care le aveam de înainte și voi folosi construcția de concatenare pentru a le combina. Vezi asta? Deci acum am automat un NFA care face limbajul al cărui șir este doar ab, doar șirul ab. Și nu este cel mai simplu NFA. Poti sa faci unul mai simplu, dar virtutea acestuia este ca am obtinut-o automat doar urmarind constructia inchiderii. Așa că acum am de gând să fac una mai complexă, doar la interior aici, o uniune ab. Deci modul în care voi construi asta este din cele două părți, partea a și partea ab, partea a și partea ab. Deci aici este partea a. Iată partea ab. Le am deja pe alea de înainte. Este într-adevăr o dovadă prin inducție aici. Dar cred că este destul de simplu, nu trebuie să folosim acel limbaj. Deci avem partea a, partea ab. Și acum vom aplica închiderea în construcție unioară pentru a le combina într-o singură mașină. Și amintiți-vă cum a funcționat. Aveam un simbol nou aici, care se ramifică sub șir gol la precedentul -- adăugăm o nouă stare de pornire, care se ramifică la stările de început inițiale sub tranziție goală. Și acum aceasta este un NFA pentru această limbă, un sindicat ab. Și, în sfârșit, acum suntem la un pas de a obține steaua asta. Și cum vom face asta? Vom lua chestia asta aici și vom aplica construcția pentru închiderea cu stea. Și asta va fi o NFA care face o uniune ab star, ceea ce ne-am dorit în primul rând. Așa că, mai întâi, o vom reduce pe aia. Pentru că deja l-am construit pe acela. Și acum amintiți-vă cum am construit închiderea sub stea. Am făcut ca stările de acceptare să revină la starea de pornire și am adăugat o nouă stare de pornire pentru a ne asigura că avem șirul gol care a trecut la starea inițială de pornire sub epsilon. BINE? Deci, asta este tot ce am vrut să spun pentru prelegerea de astăzi. Să facem o recenzie rapidă. Concept foarte important , nondeterminism și automate finite nedeterministe -- am demonstrat că sunt echivalente în putere, am arătat clasa de limbaje obișnuite închise sub concatenare în stea. Am arătat cum să facem conversia expresiilor regulate în NFA. Deci cred că asta este pentru prelegerea de astăzi. Și vă mulțumesc tuturor pentru că sunteți aici. Voi încerca să răspund la câteva dintre acestea. „De ce concatenarea are ordine?” Ei bine, pentru că este o construcție ordonată. Există o modalitate simplă de a demonstra închiderea sub concatenare fără a utiliza nondeterminism? Nu. „De ce șirurile goale sunt în starea de acceptare? Nu pot fi în nicio stare? Nu steaua face copii ale vreunei părți a intrării?” Nu, este doar... trebuie să te gândești la ce se întâmplă. Trebuie să ramificați înapoi la început doar pe o acceptare. Pentru că asta înseamnă că ai găsit o piesă care este în limba originală. „Există un automat care să adauge sau să scadă automate de memorie?” Ei bine, depinde ce vrei să spui prin toate astea. Dar cu siguranță, există mașini mai puternice pe care le vom studia decât automatele finite. Dar da, există. Și chiar și automatele finite pot adăuga și scădea, dacă prezentați intrarea în modul corect. Te-aș trimite la prima problemă la teme. Deci cred că o să verific atunci. Aveți grijă, toată lumea. Pa! Pa.