[SCRÂTÂND] [FOȘIT] [CLIC] MICHAEL SIPSER: Deci, bine ați venit, tuturor, la Introducere online în Teoria Calculului 18.404/6.840, toamna 2020. Numele meu este Mike Sipser. O să fiu instructorul tău pentru semestrul din această clasă. Așa că permiteți-mi doar să vă spun despre ce este cursul. Practic, va fi în două jumătăți. Vom vorbi despre care sunt capabilitățile și limitările computerelor -- ale algoritmilor de computer, de fapt, de calcul. Și cele două părți ale cursului sunt mai mult sau mai puțin împărțite în jumătate. Prima jumătate a cursului va vorbi despre un subiect numit teoria computabilității, care întreabă cu adevărat ce puteți calcula cu un algoritm în principiu. Aceasta a fost o zonă activă de cercetare în prima parte a secolului al XX-lea. Este aproape închis ca subiect de cercetare în aceste zile, în principal pentru că au răspuns la toate întrebările lor mari. Și astfel un domeniu matematic rămâne într-adevăr vital doar atunci când are probleme de rezolvat și ei și-au rezolvat cu adevărat toate problemele lor interesante -- în cea mai mare parte, nu 100%. Dar, în cea mai mare parte, s-a terminat oarecum în anii 1950-- doar pentru a spune puțin mai multe despre ceea ce vom vorbi acolo. Când sunteți interesat să știți ce tipuri de probleme puteți rezolva cu un algoritm, există probleme pe care ați putea dori să le rezolvați și pe care pur și simplu nu le puteți rezolva. De exemplu, având în vedere o specificație pentru o problemă de computer pe care doriți să o rezolvați, oricare ar fi specificația respectivă - să spunem că algoritmul dvs. este de fapt un algoritm de sortare, de exemplu - și doriți să notați specificația respectivă și să aveți un verificator automat care va funcționa pentru a verifica dacă un program îndeplinește specificațiile. Ei bine, acest lucru este, în principiu, imposibil. Nu puteți face un verificator care să răspundă, în toate cazurile, dacă un program îndeplinește sau nu o anumită specificație. Deci, cu astfel de lucruri, vom dovedi semestrul acesta. Întrebări despre adevărul matematic -- dacă vi se oferă o afirmație matematică, este adevărată sau este falsă? Ar fi grozav dacă ai putea scrie un program de calculator care să răspundă la această problemă. Ei bine, n-ar fi grozav dacă ai fi matematician, pentru că asta ne-ar scoate pe toți din afaceri. Dar vă puteți imagina că ar putea fi un lucru frumos, dar nu puteți. Adică, nu există un algoritm care să poată răspunde la această întrebare. Ei bine, pe parcurs, vom introduce modele de calcul, cum ar fi automate finite, pe care le vom vedea astăzi, mașinile Turing și alte modele pe care le vom vedea pe parcurs. În a doua jumătate a cursului, care va avea loc după semestrul, vom schimba vitezele și vom vorbi despre teoria complexității, care în loc să ne uităm la ceea ce este computabil în principiu, veți vedea ce este calculabil în practică, deci lucruri pe care le poți rezolva într-un timp rezonabil. Și, de exemplu, sunt sigur că mulți dintre voi sunt conștienți de problema factoring, care are conexiuni la criptosistemul RSA, criptografie și vă întreabă dacă puteți factoriza rapid numere mari. Aceasta este o problemă la care nu știm răspunsul. Pur și simplu nu știm cum să factorăm rapid numerele mari. Dar este posibil să existe algoritmi pe care nu i-am descoperit încă care să poată face acest lucru. Este legat de această problemă foarte faimoasă din intersecția dintre informatică și matematică numită problema P versus NP, despre care mulți dintre voi probabil ați auzit. Vom vorbi despre asta. Vom petrece mult timp în acest termen. Și pe parcurs, vom vorbi despre diferite măsuri de complexitate, de calcul, timp și spațiu, timp și memorie, memorie teoretică, spațiu electric. Aceasta va fi o mare parte a cursului în partea de teoria complexității - introduceți alte modele de calcul, cum ar fi calculul probabilistic și interactiv. Vorbiți despre așteptările cursului. În primul rând, condițiile prealabile. Sunt enumerate o grămadă de cerințe preliminare, 6.042, 18.062 sau poate și un alt subiect. Adevărat este că aceasta este o clasă de matematică. Aceasta este o clasă în care... și nu este o clasă de matematică pentru început, aceasta este o clasă de matematică de la nivel moderat până la avansat . Și mă aștept ca oamenii să fi avut o experiență anterioară, de natură substanțială, cu teoreme și dovezi matematice. Vom începe încet, dar vom crește destul de repede. Deci, dacă nu ați înțeles cu adevărat ideea sau nu v-ați simțit confortabil să faceți dovezi, să veniți cu dovezi pentru enunțuri matematice, asta va fi o îngrijorare. M-aș monitoriza pe tine și aș vedea cum te descurci. Pentru că temele și examenele vor conta pe faptul că poți produce dovezi și așa te vei lupta dacă asta va fi un lucru real... cu care nu ai avut experiență. Și permiteți-mi să vorbesc puțin despre rolul teoriei în informatică. Aceasta este o clasă de teorie, după cum știți. Așa că, înainte de a trece la material, m-am gândit că ar merita să vă oferiți cel puțin perspectiva mea asupra rolului informaticii teoretice în domeniu. Așa că sunt în informatică de multă vreme. Mă întorc... Sunt sigur că voi deveni un dinozaur aici... dar mă întorc la vremurile când aveai cărți perforate. Așa făceam noi când eram universitar. Și, evident, lucrurile stau foarte diferit acum. Și puteți argumenta că informatica ca disciplină s-a maturizat și un fel de lucruri de bază au fost rezolvate. Ei bine, aș spune că există un anumit adevăr în asta, dar există un anumit fel în care aș spune că nu este adevărat. Cred că suntem încă la începutul, cel puțin în anumite privințe, al informaticii ca disciplină. În primul rând, există o mulțime de lucruri pe care le facem, o mulțime de lucruri legate de calcul, la care pur și simplu nu știm răspunsul la - lucruri foarte fundamentale. Să luăm ca exemplu cum funcționează creierul? Evident, creierul calculează într-un anumit mod. Și am făcut progrese bune, puteți argumenta, cu învățarea automată și toate acele lucruri care au foarte-- foarte puternice și fac lucruri foarte interesante. Dar aș mai spune că la un nivel mai profund, metodele pe care le avem până acum nu ne permit să înțelegem creativitatea. Nu suntem aproape de a putea crea un program de calculator care poate face matematică sau care poate face multe dintre lucrurile creative pe care le pot face ființele umane. Cred că învățarea automată, oricât de puternică este, are cu adevărat succes doar pentru un set foarte restrâns de sarcini. Și cred că probabil că se întâmplă ceva mai profund și mai fundamental, care ne lipsește. Asta ar fi bănuiala mea. Acum, dacă ceva de genul informatică teoretică vă va da un răspuns acolo -- sau acest tip de teorie, sau un fel de teorie -- cred că un fel de teorie are cel puțin o șansă decentă de a juca un rol în a ne ajuta pentru a înțelege calculul într-un mod mai profund. Și faptul că nu putem înțelege ceva atât de elementar , poți să factorizezi un număr mare rapid sau nu? Nu poți spune cu adevărat că înțelegi calculul până nu poți răspunde la astfel de întrebări. Așadar, aș susține că avem o înțelegere foarte primitivă a calculului în această etapă și că mai sunt multe de descoperit, nu doar din partea tehnologică, ci doar din partea teoretică fundamentală, care are o posibilitate reală. în a juca un rol în afectarea practicii modului în care folosim computerele. Și deci cred că din acest motiv... din nou, nu sunt sigur ce fel de teorie va fi cel mai util, dar teoria pe care o vom acoperi în acest curs este o teorie deosebit de elegantă și a făcut-o deja a avut roade în multe aplicații și în ceea ce privește înțelegerea noastră a calculului. Și cred că, cel puțin ca punct de plecare, este o materie bună de învățat. Cu siguranță, îmi place și mi-am petrecut o bună parte din cariera făcând asta. Deci, să trecem mai departe și să începem cu materialul subiectului. Așa că vom vorbi despre modele de calcul, așa cum am menționat. Vrem să încercăm să înțelegem computerele și vrem să înțelegem ce pot face computerele. Dar computerele din lumea reală sunt obiecte destul de complicate și nu e chiar drăguț să vorbești despre ele matematic. Așa că vom vorbi despre modele abstracte de computere care sunt mult mai simple, dar cu adevărat captează -- la fel ca modelele în general -- surprind aspectele importante ale lucrurilor pe care încercăm să-l înțelegem. Așa că ne vom uita la mai multe tipuri diferite de modele care variază în ceea ce privește capacitățile lor și modul în care aproximează computerele reale cu care ne confruntăm în fiecare zi. Și pentru început, ne vom uita la un model foarte simplu numit automatul finit. Și asta va reprezenta... vă puteți gândi la el ca reprezentând un computer care are o cantitate foarte mică de memorie și o cantitate foarte limitată și mică de memorie. Și ne vom uita la capacitățile acestor tipuri de mașini. Și ce e frumos la ei este că îi poți înțelege foarte bine. Și așa că modelele mai puternice pe care le vom analiza mai târziu vor fi mai greu de înțeles într-un mod cât mai profund. Dar pentru acestea, putem dezvolta o teorie foarte cuprinzătoare. Și așa vom face pentru următoarea prelegere și jumătate. Așa că încep cu un exemplu. Vă prezint un automat finit ca o diagramă -- îl numim diagramă de stări. Are aceste cercuri și linii și etichete pe linii și, de asemenea, pe aceste cercuri. Deci ce se întâmplă aici? Deci acesta este un automat finit. Îi dau numele M1. Și are... aceste cercuri se numesc stări. Deci, în acest caz, au existat trei stări, q1, q2 și q3. Astea sunt etichetele de acolo. Există săgeți care leagă state între ele. Deci pe acestea le vom numi tranziții. Și vă vor spune cum să calculați cu acest dispozitiv. Și va exista o stare de pornire special desemnată , care are o săgeată care vine de nicăieri. Și există și alte stări special desemnate numite stări de acceptare, iar asta va avea de-a face cu modul în care mașina calculează. Dar aceia sunt cei care au aceste cercuri duble. Deci, vorbind despre modul în care calculează, ideea este destul de simplă. Intrarea va fi un șir finit de 0 și 1, în acest caz. S- ar putea să avem și alte tipuri de simboluri care sunt permise pentru alte automate, dar exemplul pe care îl am aici, va fi 0 și 1. Și modul în care calculezi cu chestia este că pui mai întâi degetul -- ceea ce nu pot face pe Zoom, așa că voi folosi indicatorul -- pui indicatorul pe starea de pornire, cea care are săgeata care vine înăuntru de nicăieri. Mai întâi, puneți indicatorul acolo. Și apoi începi să citești simboluri din intrare, unul după altul. Deci, să luăm un exemplu aici, 01101. Așa că începeți să citiți acele simboluri și urmați acele tranziții. Deci treci 0-- și revii la aceeași stare. Apoi mergi-- următorul simbol este 1, așa că treci la această stare, de la q1 la q2. Acum ai încă unul care vine. Deci acum începi de la q2, mai ai unul, așa că urmărești tranziția asociată. Deci, dacă observați, fiecare stare are o tranziție de ieșire pentru 1 și o altă tranziție de ieșire pentru 0. Deci, există întotdeauna unde să mergeți de fiecare dată când citiți simboluri din intrare. Deci acum ești la q2. Citiți în continuare acel al treilea simbol, care este un 1. Asta vă va duce la q3. Și acum aveți un 0, care vă duce înapoi la locul în care ați fost, și un alt 1, care vă duce înapoi la locul în care ați fost. Și pentru că ai ajuns la o acceptare, spui că acceptăm acel șir. Deci asta va fi rezultatul acestui automat finit. Pentru fiecare șir, fie îl va accepta, fie îl va respinge. Deci este doar o decizie binară care va fi luată. Este un fel de ieșire 1 sau 0, dar o numim acceptare sau respingere. Deci, acesta de aici, pentru că a ajuns la starea de acceptare, este acceptat. Dar dacă te uiți la al doilea exemplu, 00101, deci vei avea 0, 0, 1, 0, 1. Acum am ajuns la q2. Asta nu este o stare de acceptare. Prin urmare, spunem că respingem această intrare. BINE? Foarte simplu. Și acum, de exemplu, una dintre întrebările pe care ați dori să le puneți, având în vedere unul dintre aceste lucruri, este, ei bine, care sunt exact acele șiruri pe care mașina le acceptă? Și puțină gândire te va ajuta să înțelegi că singurele șiruri care te vor duce la q3 sunt acele șiruri care au un 11 care apare undeva pe parcurs, două 1 consecutive și vei ajunge în starea de acceptare. Vă încurajez să vă gândiți la asta un minut, dacă nu este imediat evident. Dar acestea sunt șirurile care vor fi acceptate de această mașină. Și numim acea colecție de șiruri limbajul mașinii. Deci setul A al acelor șiruri care au un 11, pentru această mașină specială, este limbajul lui M1. Mai spunem că M1 recunoaște acel limbaj, recunoaște A. Și în ceea ce privește notația, scriem că A este L din M1. A este limbajul lui M1. Deci, limbajul unei mașini este exact setul de șiruri pe care le acceptă mașina. BINE? Deci, unul dintre primele lucruri pe care vom dori să le putem face este să luăm o mașină și să înțelegem care este limbajul ei, care este setul de șiruri pe care îl acceptă acea mașină. Un alt lucru pe care am putea dori să-l facem este, având în vedere o limbă, să construim o mașină care să recunoască limbajul respectiv. Și apoi înțelegând, care sunt clasa de limbi? Puteți obține orice limbă de la o mașină sau vor exista unele limbi pe care le puteți face și alte limbi pe care nu le puteți face? Deci, acestea sunt tipurile de întrebări pe care le vom pune despre aceste automate finite. Ce fel de lucruri pot face acele mașini și ce nu pot face? BINE. Iată următorul nostru check-in. Așa că trezește-te, toți cei care nu sunt atenți. Urmează un check-in. Deci avem mai multe întrebări, deși nu pot să păstrez... sunt aceste trei afirmații echivalente? Ce trei afirmații? PUBLIC: În partea de jos a diapozitivului. MICHAEL SIPSER: O, o, o, o, o, da. Cele trei sunt echivalente. A este limba... da, acestea înseamnă același lucru. Nu numai că sunt echivalente, dar sunt doar moduri diferite de a spune același lucru. Că M1 recunoaște limbajul este același lucru cu a spune că acesta este limbajul mașinii și că A este egal cu acel L din M. E tot același mod de a spune toți -- șase din unul, jumătate de duzină din celălalt. Sunt două moduri de a spune același lucru. OK, deci haideți să deschidem sondajul nostru și să începem asta. Hopa. Îl arăt pe cel vechi... oh, iată-ne. Mutați-l la următoarea întrebare. BINE. OK, deci înțelegi întrebarea de aici? Unde ajungem după ce citim 101? În ce stare suntem? Ajungem în starea q1, q2 sau q3? BINE? Du-te repede. Acesta este un... OK, deci cred că am ajuns aproape aici. Cred că aproape toată lumea a avut dreptate. Răspunsul este într-adevăr că ai ajuns în starea q2. Pentru că mergi cu 1, 0, 1 și acolo ai ajuns, în starea q2. Deci este acceptat acest șir? Nu, pentru că nu ai ajuns într-o stare de acceptare. Deci mașina asta respinge 101. OK, să continuăm. Deci acum... da. OK, așa că acum i-am dat această idee informală a unui automat finit. Va trebui să încercăm să obținem o definiție formală acum, care va fi un mod mai matematic de a spune același lucru pe care tocmai l-am spus. Și motivul pentru care avem o definiție formală este, în primul rând, că ne permite să fim foarte precisi. Apoi vom ști exact ce înțelegem prin un automat finit și ar trebui să răspundă la orice întrebări despre ce contează și ce nu contează. Este, de asemenea, o modalitate de a furniza notație. Deci, ne va ajuta să descriem automatele finite. Și uneori ar putea exista un automat în care imaginea este prea mare, așa că ați putea dori să o puteți descrie într-o terminologie matematică, mai degrabă decât oferind o imagine. Sau poate vi se va cere să oferiți o familie de automate, unde va exista un parametru, N, asociat cu clasa de limbaje pe care încercați să o descrieți cu automatul. Și atunci va fi mai util să o descriem în această notație formală, mai degrabă decât ca un fel de imagine, pentru că ar putea fi nevoie de un număr infinit de imagini . Deci, poate că vor apărea exemple în acest sens acum. Deci un automat finit, îl numim un tuplu de 5. Nu te lăsa descurajat de asta. Un tuplu de 5 este doar o listă de cinci lucruri. Deci, un automat finit, în definiția noastră, va avea cinci componente. Va avea Q, care va fi un set finit de stări, deci va fi o mulțime finită, pe care o vom desemna drept stări ale automatului. Sigma este simbolurile alfabetice ale automatului, un alt set finit. Delta este funcția de tranziție. Asta ne spune cum se deplasează automatul de la o stare la alta. Acestea descriu modul în care acele săgeți de tranziție - acele săgeți care conectau stările între ele - le descrie într- un mod matematic, în loc de o imagine. Și modul în care fac asta este cu o funcție. Deci delta este o funcție care necesită două lucruri. Așa că sper că ați mai văzut această notație. Te voi ajuta o dată să treci peste asta, dar acesta este genul de lucru pe care m-aș aștepta să fi văzut deja. Deci avem Q cross sigma. Așa că voi da lui delta o stare și un simbol alfabetic. Deci Q este stări, sigma este simboluri alfabetice. Deci veți obține o stare și un simbol alfabetic și vă va da înapoi o stare. Deci, descriindu-l un pic mai detaliat, delta, dacă îi dai starea q și simbolul a este egal cu r, înseamnă q, când citești un a, mergi la r. Așa este modul în care această imagine este tradusă într-o funcție matematică, care descrie acele tranziții. Și acum q0 va fi starea de pornire. Este cel cu săgeata care vine de nicăieri. Și F este mulțimea stărilor de acceptare. Deci va exista o singură stare de pornire, dar ar putea exista mai multe stări de acceptare diferite sau chiar 0 . Totul este legal când avem un automat finit. Și așadar, în ceea ce privește utilizarea notației -- revenind la mașina pe care tocmai o aveam din diapozitivul anterior, pe care v-am dat-o din nou aici -- permiteți-mi să vă arăt cum aș descrie acest lucru folosind această notație care iese din definitia. Deci, aici este M1 din nou. Este acest 5-tuplu în care Q acum este mulțimea-- q1, q2, q3-- acesta este setul de stări. Alfabetul de intrare este 0, 1. Poate varia la alte automate. Și f este mulțimea q3, care are doar elementul q3, deoarece acesta are o singură stare de acceptare, q3. Așa că sper să fie de ajutor. Oh, bineînțeles, am uitat funcția de tranziție, pe care aici o descriu ca un tabel. Deci, funcția de tranziție spune că dacă aveți o stare și un alfabet de intrare, puteți căuta în tabel unde ar trebui să mergeți sub funcția de tranziție în funcție de starea și simbolul alfabetului pe care vi-l este dat. Deci, de exemplu, dacă am fost în starea q2 aici obținem un 0, atunci q2 se întoarce la q1, astfel încât q2 pe 0 este q1. Dar q2 pe 1 aici este q3. BINE? Așa că tabelul surprinde această imagine. BINE? Și este doar o funcție. Este o modalitate de a reprezenta o funcție, o funcție finită, în termenii acestui tabel de aici. Așa că îmi dau seama, pentru unii dintre voi, acest lucru poate fi lent. Vom crește viteza, dar încerc să ne adun pe toți în ceea ce privește limba cursului aici la început. OK, deci acum să mai vorbim despre calcul, deci șiruri și limbaje. Un șir este doar o secvență finită de simboluri din alfabet. Această clasă nu va vorbi despre șiruri infinite. Toate șirurile noastre vor fi finite. Există și alte teorii matematice ale automatelor și așa mai departe care vorbesc despre intrări infinite și șiruri infinite. Nu vom vorbi despre asta. Poate rar, vom spune foarte clar, vom vorbi despre un șir infinit, dar asta va fi o excepție. Și o limbă este un set de șiruri. Acesta este modul tradițional în care oamenii din acest subiect se referă la un set de șiruri. Ei o numesc limba -- de fapt pentru că subiectul își are rădăcinile în lingvistică, de fapt. Și vorbeau despre... ei încearcă să înțeleagă limbile, limbile umane. Deci acesta este doar un fapt istoric și aceasta este terminologia care a rămas blocată. OK, deci două șiruri speciale - un șir special și un limbaj special. Șirul gol este șirul de lungime 0. Acesta este un șir total legitim cu care veți întâlni din când în când. Și există limbajul gol, care este setul fără șiruri. Acestea nu sunt la fel. Nici măcar nu sunt de același tip de obiect. Deci nu le confundați unul cu altul. Adică, poți avea un set, un limbaj, care are doar un element, care este șirul gol. Acesta nu este setul gol. Acesta este un set - nu este limbajul gol. Acesta este un limbaj care are un element în el, și anume șirul gol. Deci sunt lucruri separate. Bine, deci aici este o gură mai mică aici pe diapozitiv, care definește ce înseamnă pentru un automat să-și accepte intrarea-- acceptă șirul său de intrare w. Și putem defini asta formal. Și are un aspect puțin tehnic, chiar nu e chiar așa de rău. Deci, dacă aveți șirul dvs. de intrare w, pe care îl puteți scrie ca o secvență de simboluri în alfabet - w1, w2, punct punct punct , wn, așa cum ar fi 01001. Îl scriu doar simbol cu ​​simbol aici. Deci, ce înseamnă pentru mașină să accepte acea intrare? Deci asta înseamnă că există o secvență de stări în mașină, o secvență de stări ale membrilor lui Q. Deci o secvență din Q, acestea sunt stările mașinii care satisfac aceste trei proprietăți aici. În primul rând, și mă gândesc la secvența prin care trece mașina în timp ce procesează intrarea w. Deci, când acceptă w? Dacă acea secvență are caracteristica că începe la starea de început, fiecare stat urmează legal starea anterioară conform funcției de tranziție. Așadar, se spune că al-lea membru al secvenței este obținut uitându-se la cel anterior -- i minus primul membru al acelei secvențe, i minus prima stare din acea secvență -- și apoi uitându-se la ceea ce se întâmplă când luați i-al-lea simbol de intrare. Deci, pe măsură ce vă uitați la starea anterioară și la următorul simbol de intrare, ar trebui să obțineți următoarea stare. Asta e tot ce spune asta. Și asta ar trebui să se întâmple pentru fiecare dintre acești tipi. Și, în sfârșit, pentru ca acest lucru să fie acceptat, ultimul membru de aici, unde am ajuns la sfârșitul intrării-- așa că îți pasă de asta doar la sfârșitul intrării-- trebuie să fii într- o stare de acceptare. Deci, puteți captura matematic această noțiune de a merge pe această cale. Și asta e ceea ce-- Încerc doar să ilustrez că am putea descrie toate acestea foarte formal-- Nu spun că acesta este cel mai bun mod de a gândi la asta tot timpul-- dar că se poate face. Și cred că este ceva ce merită apreciat. BINE. Deci, acum, în ceea ce privește, din nou, revenirea... am spus asta deja o dată , dar în ceea ce privește limbajele pe care le recunoaște mașina, este colecția de șiruri pe care mașina o acceptă. Fiecare mașină acceptă -- ar putea accepta multe șiruri, dar recunoaște întotdeauna o anumită limbă, chiar dacă mașina nu acceptă șiruri -- atunci recunoaște limba goală. Deci o mașină recunoaște întotdeauna o limbă, dar poate avea multe, multe șiruri pe care le acceptă. Și o numim limbajul mașinii. Și spunem că M recunoaște acel limbaj. Aceste trei lucruri înseamnă același lucru. BINE? Și acum definiție importantă-- Încerc să rezerv cele mai importante lucruri sau cele evidențiate să fie în această culoare albastru deschis, dacă puteți vedea asta. Spunem că o limbă este o limbă obișnuită dacă există un automat finit care o recunoaște. BINE? Deci vor exista unele limbi care le-au asociat automate finite care rezolvă de fapt acele limbi, care recunosc acele limbi. Dar ar putea exista și alte limbi -- și vom vedea exemple -- în care pur și simplu nu le puteți rezolva. Nu le poți recunoaște cu un automat finit. Aceste limbi nu vor fi limbi obișnuite. Cele obișnuite sunt cele pe care le poți face cu un automat finit. Aceasta este terminologia tradițională. OK, deci hai să continuăm. Să mergem mai departe de acolo. Deci hai să facem câteva exemple. Iată, din nou, același lucru... a devenit un vechi prieten, acel automat M1. Amintiți-vă, limbajul său aici este setul de șiruri care au subșirul 11. Acesta este limbajul A. Acum, ce știm despre A din diapozitivul anterior? Gândește-te cu mine. Nu asculta doar. A este un limbaj obișnuit acum, pentru că este recunoscut de un automat. Deci, ori de câte ori găsiți un automat pentru o limbă, un automat finit pentru limbaj, știm că acel limbaj este un limbaj obișnuit. Așa că să ne uităm la alte câteva exemple. Deci, dacă luați limba -- să-l numim pe acesta B, care sunt șirurile care au un număr par de 1 în ele. Deci, la fel ca șirul 1101, ar fi acesta în B? Nu, pentru că are un număr impar de 1. Deci șirul 1111 are patru 1-uri în el. Acesta este un număr par, astfel încât acel șir ar fi în B. 0-urile nu contează pentru acest limbaj. Deci șiruri care au un număr par de 1, acesta este un limbaj obișnuit. Și modul în care ai ști asta este că ar trebui să faci un automat finit care să recunoască limbajul respectiv. Și te-aș încuraja să mergi și să faci acel automat. O poți face cu două stări. Este un automat foarte simplu. Dar dacă nu ai făcut practică cu acestea, te încurajez să faci asta. Și, de fapt, există o mulțime de exemple pe care vă cer să le rezolvați la sfârșitul capitolului 1 din carte și cu siguranță ar trebui să petreceți ceva timp jucându-vă cu ele dacă nu ați văzut încă automate finite înainte. Trebuie să te simți confortabil cu acestea și să le poți face. Așa că vom începe să facem unele dintre ele, dar vom vorbi despre asta la un fel de nivel mai abstract într-un minut. Practic, motivul pentru care puteți rezolva această problemă, puteți face un automat finit care recunoaște limbajul B, este pentru că acel automat finit va ține evidența parității numărului de 1 pe care le-a văzut înainte. Aceasta are două stări, una dintre ele amintindu-și că a văzut un număr impar de 1 până acum, cealaltă amintindu-și că a văzut un număr par de 1 înainte. Și asta va fi tipic pentru aceste automate, automate finite. Vor exista mai multe posibilități diferite pe care este posibil să trebuiască să le urmăriți în timp ce citiți intrarea și va exista o stare asociată cu fiecare dintre aceste posibilități. Deci, dacă proiectați un automat, trebuie să vă gândiți -- în timp ce procesați intrarea -- la ce lucruri trebuie să urmăriți. Și vei face o stare pentru fiecare dintre aceste posibilități. BINE? Deci trebuie să te simți confortabil cu asta. Să ne uităm la un alt exemplu, limbajul C în care intrările au un număr egal de 0 și 1. Se dovedește a nu fi un limbaj obișnuit. Deci, cu alte cuvinte, ceea ce înseamnă că nu există nicio modalitate de a recunoaște limbajul cu un automat finit. Pur și simplu nu o poți face. Asta depășește capacitățile automatelor finite. Și aceasta este o afirmație pe care o vom demonstra mai târziu. BINE. Iar scopul nostru la următoarea prelegere este să înțelegem limbile obișnuite, lucru pe care îl puteți face într-un mod foarte cuprinzător. Deci vom începe să facem asta acum. Așa că, mai întâi, vom introduce acest concept de expresii regulate - care, din nou, acestea sunt lucruri pe care le-ați mai întâlnit într-un fel sau altul înainte. Așa că vom introduce ceva numit operațiuni obișnuite. Acum, sunt sigur că ești familiarizat cu operațiile aritmetice, cum ar fi plus și timpi. Acestea se aplică numerelor. Operațiunile despre care vom vorbi sunt operațiuni care se aplică limbilor. Deci ei vor lua, să zicem, două limbi, aplicați o operație, veți recupera o altă limbă. Ca și operațiunea sindicală, de exemplu, probabil că ați mai văzut-o. Uniunea a două limbi aici este o colecție de șiruri care sunt fie într-una, fie în alta. Dar există și alte operațiuni, pe care poate nu le-ați văzut înainte, pe care le vom analiza -- operația de concatenare, de exemplu. Deci, asta spune că vei lua un șir din prima limbă și un alt șir din a doua limbă și le vei lipi. Și se numește concatenarea lor. Și faci asta în toate modurile posibile și vei obține limbajul de concatenare din aceste două limbi cu care începeți, A și B. Simbolul pe care îl folosim pentru concatenare este acest cerc mic. Dar, de multe ori, nu. Pur și simplu suprimăm asta și scriem cele două limbi una lângă alta, cu micul cerc implicat. Deci asta înseamnă și concatenare aici, la fel cum face asta. Iar ultima dintre operațiunile obișnuite este așa-numita operație stea, care este o operațiune unară. Se aplică doar unei singure limbi. Și deci ceea ce faceți este că acum veți lua... pentru a obține un membru al limbajului vedetă, veți lua o grămadă de șiruri în limba originală, A, le lipiți împreună. Orice număr de membri ai lui A, îi lipiți împreună, iar asta devine un element al limbajului vedetă. Și vom face un exemplu într-o secundă dacă nu ați înțeles asta. Dar un element important este că, atunci când aveți limbajul stea, îi puteți, de asemenea, să îi permiteți să lipească zero elemente împreună, iar apoi obțineți șirul gol. Deci, acesta este întotdeauna un membru al limbajului stelelor, șirul gol. Bine, deci să ne uităm la câteva exemple. Să presupunem că A este limbajul - acestea sunt două șiruri aici - bine, rău. Și B este limba băiat, fată. Acum, dacă luăm unirea celor doi, ajungem bun, rău, băiat, fată. La asta te-ai aștepta. Și acum să aruncăm o privire la concatenare. Acum, dacă concatenați limbajul A și B, veți obține toate modalitățile posibile de a avea un șir A urmat de toate modurile posibile de a avea un șir B. Așa că poți obține băiat bun, fată bună, băiat rău, fată rea. Acum, privind stea, ei bine, asta se aplică doar unei limbi. Deci, să presupunem că este limbajul bun, rău de la A. Și astfel, steaua A pe care o obțineți din asta este toate modalitățile posibile de a lipi șirurile de la A. Deci, folosind fără șiruri, obțineți întotdeauna șirul gol. Este întotdeauna garantat să fii membru al lui A. Și apoi, luând doar un element din A, vei obține bine, sau alt element, rău. Dar acum două elemente ale lui A, obțineți bun, bun sau bun, și așa mai departe. Sau trei elemente ale lui A, bine, bine, bine, rău. Și astfel, de fapt, O stea va fi un limbaj infinit dacă A însuși conține vreun membru nevid. Deci, dacă A este limbajul gol sau dacă A conține doar șirul gol al limbajului , atunci O stea nu va fi un limbaj infinit. Va fi doar șirul gol al limbii. Dar altfel, va fi un limbaj infinit. Nici măcar nu sunt sigur... OK. Nu sunt... [Râde] Ignor chatul de aici. Sper că oamenii primesc... Băieți, primiți răspunsuri la întrebările voastre de către AT-ul nostru? Ce mai facem, Thomas? PUBLIC: O întrebare este, vor fi postate diapozitivele? MICHAEL SIPSER: Diapozitivele vor fi postate? Ei bine, întreaga prelegere va fi înregistrată. Este util să aveți diapozitivele separat? Pot posta diapozitivele. Sigur. Amintește-mi dacă nu o fac, dar voi încerca să fac asta. Da, este de ajutor. Voi face asta. Da. Da, voi posta diapozitivele. Doar, Thomas, e treaba ta să-mi amintești. PUBLIC: OK. MICHAEL SIPSER: Bine, bine. Așa că am vorbit despre operațiunile obișnuite. Să vorbim despre expresiile regulate. Deci, expresiile regulate sunt -- la fel cum aveți operațiile aritmetice, atunci puteți obține expresii aritmetice, cum ar fi 1 plus 3 ori 7. Deci acum vom face expresii din aceste operații. În primul rând, aveți, cu atât mai multe lucruri atomice, blocurile de construcție ale expresiilor, care vor fi ca elementele sigma, elementele alfabetului sau sigma în sine ca simbol al alfabetului, sau limbajul gol sau șirul gol. . Acestea vor fi elementele de bază ale expresiilor regulate. Vom face un exemplu într-o secundă. Și apoi combini acele elemente de bază folosind operațiile obișnuite de unire, concatenare și stea. Deci acestea sunt expresiile atomice, acestea sunt expresiile compuse. Deci, de exemplu, dacă te uiți la expresia 0 union 1 stea-- așa că putem scrie și ca stea sigma. Pentru că dacă sigma este 0 și 1, atunci steaua sigma este același lucru cu 0 union 1-- sigma este același cu 0 union 1. Și asta dă doar toate șirurile posibile peste sigma. Deci, acesta este ceva ce veți vedea frecvent. Steaua Sigma înseamnă că acesta este limbajul tuturor șirurilor din alfabetul cu care lucrăm în acel moment. Acum, dacă luați stea sigma 1, doar concatenați 1 pe toate elementele stelei sigma și asta vă va oferi toate șirurile care se termină cu 1. Tehnic, vă puteți imagina că scrieți asta cu acolade în jurul lui 1, dar în general, noi nu facem asta. Noi doar... seturi de un singur element , șiruri de un singur element, scriem fără acolade, pentru că este suficient de clar fără ele și devine dezordonat cu ele. Deci sigma steaua 1 sunt toate șirurile care se termină cu 1. Sau, de exemplu, luați sigma steaua 11 sigma star, adică toate șirurile care conțin 11. Și am mai văzut acel limbaj o dată înainte. Acesta este limbajul acelei alte mașini pe care i-am prezentat unul sau două diapozitive înapoi. BINE? Dreapta. Da, dar în ceea ce privește citirile-- apropo, îmi pare rău, nu știu dacă îți este de ajutor să fac aceste interjecții-- dar citirile sunt listate și pe teme. Deci, dacă te uiți la tema 1 postată, îți spune ce capitole ar trebui să citești acum. Și, de asemenea, dacă te uiți la orarul cursurilor, care se află și pe pagina principală, are întregul plan al cursului și ce lecturi sunt pentru ce date. Deci totul este acolo pentru tine. Și deci scopul nostru aici - nu este un accident că steaua sigma 11 steaua sigma se întâmplă să fie același limbaj pe care l-am văzut înainte din limbajul acelui automat finit M1. De fapt, acesta este un fenomen general. Orice puteți face cu o expresie regulată, puteți face și cu un automat finit și invers. Ele sunt echivalente ca putere în ceea ce privește clasa de limbi pe care o descriu. Și vom demonstra asta. BINE? Deci, dacă te dai înapoi pentru o secundă și te lași să apreciezi asta, este un lucru uimitor. Pentru că automatele finite, cu stările și tranzițiile și expresiile regulate, cu aceste operații de unire, concatenare și stea, arată total diferit unul de celălalt. Se pare că nu au nimic de-a face unul cu celălalt. Dar, de fapt, ambele descriu exact limbile obișnuite, aceeași clasă de limbi. Și deci este un fapt grozav că poți dovedi că aceste două sisteme cu aspect foarte diferit sunt de fapt echivalente unul cu celălalt. Putem obține șir gol din set gol? Da. Există o grămadă de cazuri exotice, de altfel. Deci steaua limbajului gol este limba care are doar șirul gol. Dacă nu înțelegi asta, mestecă-l pe acela. Dar asta este adevărat. OK, hai să mergem mai departe. OK, să vorbim acum despre proprietățile de închidere. Vom începe să facem ceva care are puțin mai multă carne, în ceea ce privește prima noastră teoremă a cursului să vină aici. Și aceasta nu este o teoremă pentru copii. Acesta este de fapt... va fi ceva carne la asta. Și va trebui să nu... asta nu este o jucărie. Demonstrăm ceva care are substanță reală. Și enunțul acestei teoreme spune că limbajele obișnuite sunt închise, că într-adevăr, clasa de limbaje regulate este închisă sub unire, închisă sub operația de unire. Deci, ce vreau să spun cu asta? Deci, când spuneți că o colecție de obiecte este închisă sub o anumită operație, înseamnă că aplicarea acelei operații la acele obiecte vă lasă în aceeași clasă de obiecte. La fel ca numerele întregi pozitive, numerele naturale, care sunt închise la adunare. Pentru că atunci când adăugați două numere întregi pozitive, obțineți înapoi un număr întreg pozitiv. Dar nu sunt închise prin scădere. Pentru că 2 minus 4, obțineți ceva care nu este un număr întreg pozitiv. Atât de închis înseamnă că te lași în colecție. Și adevărul este că, dacă te uiți la toate limbajele obișnuite -- acestea sunt limbajele pe care automatele finite le pot recunoaște -- sunt închise sub operațiunea de unire. Deci, dacă începeți cu două limbi obișnuite și aplicați uniunea, veți reveni cu o altă limbă obișnuită. Și asta este enunțul acestei teoreme. Sper că este suficient de clar în felul în care l-am scris. Dacă A1 și A2 sunt regulate, atunci uniunea A1 A2 este de asemenea regulată. Cam asta este afirmația. Și pur și simplu, asta demonstrează că clasa de limbaj obișnuit este închisă sub unire. Deci vom demonstra asta. Deci, cum demonstrezi așa ceva? Deci, modul în care vom demonstra asta este să începi cu ceea ce presupunem. Deci ipoteza noastră este că avem două limbaje obișnuite. Și trebuie să ne dovedim concluzia, că și unirea este obișnuită. Acum, ipoteza că sunt obișnuiți, trebuie să despachetezi asta și să înțelegi, ce te aduce asta? Iar ele fiind regulate înseamnă că există automate finite care recunosc acele limbi. Deci haideți să dăm acele două nume de automate finite. Deci M1 și M2 sunt cele două automate finale care recunosc acele două limbi, A1 și A2. Asta înseamnă, că sunt regulate, că aceste automate există. Deci, să avem acele două automate, M1 și M2, folosind componentele așa cum am descris, seturile de stări respective , alfabetul de intrare, funcțiile de tranziție, cele două stări inițiale și cele două colecții de stări acceptante. Aici presupun că sunt peste același alfabet. Ați putea avea automate care funcționează pe diferite alfabete. Nu este interesant să faci asta. Nu adaugă nimic. Dovada ar fi exact aceeași. Deci, să nu ne complicăm prea mult viața și să ne concentrăm pe cazul mai interesant , presupunând că cele două alfabete de intrare vor fi aceleași. Și din aceste două automate, trebuie să arătăm că acest limbaj de aici, unirea, este și un limbaj obișnuit. Și vom face asta construind automatul care recunoaște uniunea. Acesta este cu adevărat singurul lucru pe care îl putem face. Deci vom construi un automat din M1 și M2 care recunoaște limbajul de unire A1 uniunea A2. Și sarcina lui M este că ar trebui să-și accepte intrarea dacă M1 sau M2 acceptă. Și acum, ce aș vrea să vă gândiți despre a face asta, cum naiba vom veni cu acest automat finit M? Și felul în care facem asta este să ne gândim cum ați face limbajul sindicatului? Dacă vă întreb... vă dau două automate, M1 și M2, și spun, iată o intrare, w. Este w în limba sindicatului? Aceasta este treaba pe care M ar trebui să o rezolve. Și vă sugerez să încercați să vă dați seama cum l-ați rezolva mai întâi. Adică, aceasta este o strategie bună pentru rezolvarea multor probleme din acest curs. Pune-te în locul mașinii pe care încerci să o construiești. Și așa că, dacă vrei să încerci să-ți dai seama cum să faci asta, un lucru firesc este că iei w, îl dai în M1 și apoi îl dai în M2. Și dacă M1 o acceptă, grozav, atunci știi că este în uniune. Și dacă nu, încercați-l în M2 și vedeți dacă M2 îl acceptă. Acum, trebuie să fii puțin atent, pentru că vrei să ai o strategie pe care să o poți implementa și într-un automat finit. Și un automat finit are doar o singură șansă să se uite la intrare. Nu puteți să derulați înapoi intrarea. Îl alimentezi mai întâi în M1 și apoi îl alimentezi în M2 și operezi într-un mod secvenţial astfel. Acest lucru nu va fi permis în modul în care funcționează automatele finite . Așa că va trebui să o duci la următorul nivel, să fii puțin mai deștept. Și în loc să-l alimentați mai întâi în M1 și apoi și apoi în M2, le introduceți în ambele în paralel. Deci, luați M1 și M2 și le rulați pe amândouă în paralel pe intrarea w, ținând evidența în ce stare se află fiecare dintre acele două automate. Și apoi, la sfârșit, vedeți dacă vreuna dintre acele mașini este într-o stare de acceptare. stat și apoi acceptați. Deci, aceasta este strategia pe care o vom folosi în construirea automatului finit M din M1 și M2. Deci, în ceea ce privește o imagine, iată M1 și M2. Iată automatul pe care încercăm să-l construim. Nu știm încă cum va arăta. Și da, așa că mă cam depășesc, dar iată o strategie, așa cum tocmai am descris-o, pentru că M. M va ține evidența în ce stare se află M1 și în ce stare se află M2 la un moment dat. Pe măsură ce citim simbolurile lui w, le vom introduce în M1 și, de asemenea, în M2. Și astfel, posibilitățile pe care trebuie să le urmărim în M sunt toate perechile de stări care sunt în M1 și M2, pentru că veți urmări cu adevărat M1 și M2 simultan. Deci trebuie să vă amintiți în ce stare se află M1 și, de asemenea, în ce stare se află M2. Și astfel încât asta corespunde cu adevărat ce pereche de stări să vă amintiți, una din M1 și una din M2, și de aceea am indicat așa. Deci M1 este în starea q, M2 este în starea r la un moment dat în timp. Și asta va corespunde că M este în perechea q virgulă r. Aceasta este doar eticheta acestei stări particulare de m pe care o vom aplica aici. BINE? Și atunci M va accepta dacă M1 și M2 este o stare de acceptare. Deci, se va întâmpla dacă fie q sau r este o stare de acceptare, vom transforma și aceasta într-o stare de acceptare. BINE? Hopa. Iată-ne. Așa că haideți să descriem acest lucru în mod formal și nu printr- o imagine, pentru că o putem face în ambele moduri. Și uneori este mai bine să o faci într-un fel și alteori în alt fel. Deci acum, dacă luăm-- componentele lui M acum sunt perechile de stări din M1 și M2. Din nou, scriu acest lucru literal, explicit aici, dar ar trebui să vă asigurați că vă simțiți confortabil cu această notație încrucișată. Deci aceasta este colecția de perechi de stări, q1 și q2, unde q1 este în starea primei mașini, q2 este starea celei de-a doua mașini. Starea de pornire este că porniți la cele două stări de pornire ale celor două mașini. Deci, acesta este q1, q2 - probabil că nu ar fi trebuit să reutilizam notația Q. Ar fi trebuit să-i numesc r-- acum că mă uit la asta. Dar, oricum, sper că nu sunteți confuz prin reutilizarea acestui lucru. q1 și q2 aici sunt stările de pornire specifice ale celor două mașini. Acestea sunt doar alte două state, state reprezentative ale acelor mașini. Acum, funcția de tranziție pentru noua mașină va fi construită din funcțiile de tranziție de la mașinile anterioare. Deci, când am o pereche, q, r și am simbolul a, unde mergem? Ce pereche nouă primim? Ei bine, doar actualizăm starea de la M1 și actualizăm starea de la M2 în funcție de funcțiile lor de tranziție respective, și asta este ceea ce se arată aici. Acum să aruncăm o privire la stările de acceptare pentru M. Lucrul natural de făcut este să ne uităm la setul de perechi de stări, unde avem o pereche de stări - o pereche de stări de acceptare, una de la prima mașină și una de la a doua mașină. Dar dacă te gândești cu mine, îți dai seama că acesta nu este lucrul potrivit. Ce este DFA-urile? Le-aș numi undeva DFA? Oh, probabil că altcineva face asta în chat. DFA-- atent la notație pe care o utilizați. Nu am introdus încă DFA. O vom face joia viitoare. Dar acestea sunt DFA-uri. Acestea sunt doar automate finite, automate finite deterministe. De aceea, D. Oricum, de fapt, acest lucru nu este corect, pentru că dacă te gândești la ceea ce spune asta, spune că ambele componente trebuie să accepte. Și vrei ca oricare dintre ele să accepte. Deci asta nu este bine. Acesta ar fi modul greșit de a-l defini. Asta dă de fapt limbajul de intersecție. Și într-adevăr, cam pe parcurs, se dovedește închidere sub intersecție, ceea ce nu ne pasă, dar ar putea fi util să îl avem în buzunarul din spate cândva în viitor. Pentru a obține închiderea sub o uniune, trebuie să scriem în acest mod puțin mai complicat , care spune că perechea, ceea ce vrei să ai este fie că prima stare este o stare de acceptare și apoi orice stare pentru al doilea element, sau orice stare pentru primul element și o stare de acceptare pentru al doilea element. Asta înseamnă să ai uniunea, să faci uniunea. BINE? Deci hai să facem... oh, iată o înregistrare rapidă. Deci hai să facem un alt sondaj aici. Am crezut că am terminat cu astea. Din nou... oh, iată-ne. Așa că a fost prea complicat să-l scriu în sondaje, așa că de fapt l-am pus pe diapozitiv pentru tine. Deci tot ce întreb este că dacă M1 are k1 stări și M2 are k2 stări, câte stări are M? Este suma, suma pătratelor sau produsul? OK, trebuie să te gândești la stările lui M, cum arată ele? Și haideți, băieți. Bine, încheind sondajul, partajând rezultatele. Da, într-adevăr, este... majoritatea dintre voi ați înțeles corect. Este C, produsul. Pentru că atunci când te uiți la numărul de perechi de stări din M1 și M2, ai nevoie de toate perechile posibile. Și deci este numărul de stări din M1 ori numărul de stări din M2. Așa că asigură-te că înțelegi asta și gândește-te la asta, astfel încât să urmărești și să obții asta. Bine, deci hai să mergem mai departe aici. Deci mai avem cinci minute sau cam asa ceva. Să începem să ne gândim la închidere sub concatenare. Deci, dacă avem două limbaje obișnuite, la fel este și limbajul de concatenare. Vom încerca să dovedim asta. Nu vom termina, dar măcar ne vom pune în practică sucuri creative . Deci vom face aceeași schemă aici. Vom lua două mașini pentru A1 și A2 și vom construi o mașină pentru limbajul de concatenare din cele două. Deci, iată cele două mașini pentru A1 și A2 notate. Și acum iată limbajul de concatenare. Și o să vă propun o strategie -- care nu va funcționa, dar va fi o intuiție bună. Deci ceea ce voi face este să fac o copie a... OK, să înțelegem ce ar trebui să facă M mai întâi. Deci M ar trebui să accepte intrarea sa. Deci gândește-te la asta. M face limbajul de concatenare. Deci i se dă un șir. Și trebuie să răspundă, este sau nu în limbajul de concatenare A1A2? Deci ar trebui să accepte dacă există o modalitate de a împărți w în două bucăți, unde M1 acceptă prima piesă și M2 acceptă a doua. Deci aici ar fi poza. BINE? Și acum trebuie să încercăm să facem o mașină care va rezolva această intuiție. Deci cum ai face asta singur? iti dau w. Și puteți simula M1 și M2. Așadar, lucrul firesc este că vei începe prin a simula M1 pentru un timp și apoi vei trece la simularea M2 pentru un timp, pentru că asta ar trebui să se întâmple pe măsură ce procesezi intrarea. Deci, voi sugera asta în ceea ce privește diagrama ca aceasta. Deci avem aici M1 și M2 copiate aici. Și ceea ce propun să facem este să conectăm M1 la M2, astfel încât, atunci când M1 își va accepta intrarea, să trecem la M2, pentru că aceasta este probabil prima parte a lui w. Și acum vom avea ca M2 să proceseze a doua parte a lui w. Deci, modul în care voi implementa acest lucru este prin declasificarea stării de început a lui M2, având simboluri de tranziție de la stările de acceptare ale lui M1 la M2 și apoi eliminând acești tipi de aici ca stări de acceptare. Și ar trebui să ne dăm seama ce fel de etichete să aplicăm aici. Dar, de fapt, acest raționament nu funcționează. Este tentant, dar defectuos. Pentru că... ce nu merge bine? Ce se întâmplă este că -- s- ar putea ca atunci când M1 a acceptat o parte inițială a lui w și apoi dorește ca M2 să accepte restul, ar putea eșua deoarece M2 nu acceptă restul. Și ceea ce ar fi fost mai bine să faci este să aștepți mai mult în M1, pentru că ar fi putut exista un alt loc mai târziu pentru a împărți w, care este încă valabil. Împărțirea w în primul loc în care M1 acceptă o parte inițială poate să nu fie locul optim pentru a împărți w. S- ar putea să doriți să așteptați mai târziu și atunci veți avea o șansă mai mare de a accepta w. Așa că nu sunt sigur dacă ai urmat asta. Dar, de fapt, nu funcționează. Întrebarea este unde să împărțiți w și este o provocare, pentru că de unde știți unde să împărțiți w? Pentru că depinde de ce... depinde de y și încă nu te-ai văzut. Deci, când încerci să te gândești la asta în acest fel, pare fără speranță. Dar, de fapt, este încă adevărat. Și vom vedea cum să facem asta joi. Deci, pentru a recapitula ceea ce am făcut astăzi, am făcut lucrurile noastre introductive, am definit automate finite, limbaje obișnuite. Am definit operațiile și expresiile regulate. Am arătat că limbile obișnuite sunt închise sub unire. Am început închiderea sub intersecție, pentru a continua.