Cât de practică este teoria automatelor?

1. Ați folosit vreodată un instrument precum grep / awk / sed? Expresiile obișnuite formează inima acestor instrumente.

2. Veți fi surprins cât de multe coduri puteți evita prin utilizarea principială a expresiilor regulate – în „proiecte practice”, cum ar fi un e-mail server.

3. Dacă sunteți major CS, veți scrie cu siguranță un compilator / interpret pentru o limbă (cel puțin mică). Dacă ați încercat vreodată înainte de această sarcină și ați rămas blocat, veți aprecia cât de puțină teorie (adică gramaticile fără context) vă poate ajuta. Această teorie a transformat o sarcină odată imposibilă în ceva care poate fi finalizat într-un weekend. un premiu Turing – google BNF).

4. Dacă sunteți un CS major, la un moment dat, trebuie să vă așezați și să vă gândiți la fundamentele filozofice ale computerului și nu cam cât de cool este următoarea versiune a API-ului Android. Într-o notă asemănătoare, universitatea nu are rolul de a vă pregăti pentru următorii 5 ani din viață, ci de a vă pregăti pentru următorii 50. Singurul lucru pe care îl pot face în acest sens este să vă ajute să gândiți – gândiți-vă a teoriei automatelor ca unul dintre aceste cursuri.

Una dintre cele mai practice manifestări CS este construcția compilatorului. În 1965, Knuth a început studiul analizelor LR. Rapid (în mai puțin de un deceniu), am avut analizoare LALR, care sunt un subset de automate determinist pushdown care ne permit să implementăm analize de schimbare / reducere.

În centrul fezabilității și eficienței analizei LALR se află o dovadă (de Knuth) că „prefixele” limbajului se dovedesc a fi obișnuite (automatul tău finit). Aceasta este geneza generatoarelor de parser automatizate, cum ar fi yacc / bison etc.

Iată un alt exemplu: inima protocolului TCP / IP este o mașină cu stări finite. Cât de mult mai practic poate obține?

Fiecare student serios CS, în special cei practici, ar trebui să acorde atenție teoriei automatelor. Este baza pentru o mare parte din bogăția informaticii.

Comentarii

• Analizarea fișierelor sursă nu este într-adevăr partea interesantă (și importantă) a unui compilator, așa că nu ‘ nu cred că este sigur să spunem că ” limbajele de programare așa cum le cunoaștem datorează o mare parte din eficiența de compilare acestor evoluții „. Mai mult, este posibilă analiza limbilor folosind diferite instrumente, de exemplu PEG-uri sau combinatori de analiză (adică parsec).

Puteți auzi acel zgomot ? Este sunetul a o mie de teoreme, aplicații și instrumente strălucitoare care râd în cerul teoretic al automatelor.

Limbajele și automatele sunt concepte elegante și robuste pe care le veți găsi în fiecare domeniu al informaticii. Limbajele nu sunt uscate, formaliste, din prehistoria calculelor.Perspectiva teoriei limbajului distilă întrebări aparent complicate despre obiecte sofisticate, opace, în afirmații simple despre cuvinte și copaci. Limbajele formale joacă un rol în informatică asemănător punctului de vedere fundamental și de schimbare a jocului adus de algebră și topologie matematicii clasice. Iată câteva probleme practice, destul de complicate, practice, care sunt abordate prin teoria limbajului.

1. Doriți să identificați aparițiile duplicate ale unei fraze într-un document și să ștergeți a doua apariție. În esență, doriți să înlocuiți o secvență într-o limbă.
2. Conține un program o încălcare a afirmației? Un driver de dispozitiv respectă anumite protocoale atunci când interacționează cu nucleul? Comportamentul unui program este un set de execuții; cu alte cuvinte, un limbaj. Proprietatea de corectitudine este un alt limbaj. Problema corectitudinii programului se ridică la o verificare a includerii limbajului.
3. Poate fi software-ul blocat într-o buclă infinită? Un algoritm distribuit conține un blocaj de livel? Avem nevoie de limbi peste cuvinte infinite, dar viziunea incluziunii lingvistice se aplică în continuare.
4. Doriți să construiți un dezinfectant pentru a detecta Javascript rău intenționat introdus într-o aplicație web. Setul de șiruri rău intenționate este un limbaj. Setul de șiruri a intrat în forme într-o altă limbă. Doriți să stabiliți dacă intersecția acestor limbaje nu este goală.
5. Monitorizarea în timp de execuție a sistemelor reactive și critice ale misiunii. Doriți să proiectați un monitor software care să supravegheze funcționarea procesului chimic sau să urmăriți actualizările unei baze de date financiare. Acestea sunt problemele legate de incluziunea și intersecția limbajului.
6. Recunoașterea modelelor cu numeroasele sale aplicații. Doriți să detectați tipare în datele genomice, în text, într-o serie de rapoarte de erori. Acestea sunt probleme în care ni se dau cuvinte dintr-o limbă necunoscută și trebuie să ghicim limba. Acestea sunt probleme de inferență a limbajului.
7. Având în vedere un set de documente XML, doriți să realizați o schemă care se aplică acestor documente. Documentele XML pot fi idealizate ca arbori. O schemă este apoi o specificație a unui limbaj de arbore, iar problema de inferență a schemei este o problemă de inferență de limbaj peste limbile de arbore.
8. Multe aplicații necesită un raționament aritmetic automat. Să presupunem că fixăm o teorie logică, cum ar fi aritmetica Presburger, în care avem numerele naturale, adunarea și predicatul mai mic decât. O formulă cu n variabile reprezintă un set de vectori n-dimensionali. Un vector este o secvență de cifre și poate fi codat ca un cuvânt. Un predicat este atunci un set de cuvinte; o limba. Operații logice precum conjuncția, disjuncția și negarea devin intersecție, unire și complement al limbajelor (cuantificarea existențială este un fel de proiecție).

Reducerea indicată mai sus tratează limbajele ca obiecte matematice abstracte. Pentru a aplica aceste idei în practică, avem nevoie de o structură de date pentru a reprezenta limbaje și algoritmi pentru a manipula aceste structuri de date.

Introduceți automatele. Automatele ne permit să reducem întrebările despre obiecte matematice abstracte, cum ar fi limbajele, la întrebări concrete, algoritmice, despre grafice etichetate. Limbile și teoria automatelor, pe lângă un număr nebun de aplicații practice, oferă un serviciu intelectual foarte semnificativ. Ne putem gândi la probleme care variază de la formatarea codurilor poștale la procedurile de decizie pentru logica monadică de ordinul doi într-un spațiu conceptual uniform și netezit. Cât de uimitor este asta!

Nu am spus nimic despre logică și proceduri de decizie. (Da, au aplicații practice.) Consultați răspunsul lui Kaveh pentru o imagine de ansamblu autoritară.

Comentarii

• haha, ironia

Așa cum s-a explicat în celelalte răspunsuri, teoria automatelor este importantă conceptual ca un simplu model de calcul pe care îl înțelegem bine, iar expresiile regulate și automatele au multe aplicații din viața reală.

Aici „este un mic exemplu de cercetare modernă care revine la teoria automatelor pentru a înțelege un concept modern. În această lucrare cercetătorii demonstrează că toate limbile obișnuite au testere de proprietăți: „Limbile obișnuite sunt testabile cu un număr constant de interogări”

Nu sunt doar automate vanilate. Înveți despre elementele de bază (acceptarea stărilor, tranziții epsilon, …) ale unui (de calcul) model care ajută la raționamentul despre ceea ce poate și, mai important, ce nu poate fi exprimat cu unele limbaje de interogare. Câteva rezultate interesante includ:

• da, faimosul rezultat este că Automatele finite deterministe recunosc limbile obișnuite – așa că acum știi de ce aveți nevoie pentru a implementa potrivirea expresiei regulate.
• Pushdown Automata recunoaște Gramatici fără context – acum aveți o idee despre cum arată un analizor (sau cel puțin o clasă mare dintre acestea).
• automate de copac recunoaște declarații peste logică monadică de ordinul doi – acum ai o idee despre ce este nevoie pentru a implementa câteva limbaje de programare de constrângere , sau … unele instrucțiuni în SQL , de exemplu.

(și, bineînțeles, omit mult) al altor clase)

Practic, este un model foarte general. Cursurile dvs. vor sublinia probabil legătura dintre automatele, limbile și logica.

Dacă aș fi căutat să raportez acest lucru la instrumente „lumești” concrete, aș fi petrecut o dimineață pe îndelete la bibliotecă citind câteva părți (AB?) de la Fundamentele bazelor de date de Abiteboul & al și încercând să conectați acest lucru înapoi la materialul clasei. Desigur, este doar unul dintre (multe) moduri de a căuta aplicații dintr-o clasă de automate și cred că nu este cel mai evident – dar tocmai de aceea este un exercițiu interesant.

După cum sa menționat deja în diferite răspunsuri, Teoria automatelor în cursurile UG oferă unul dintre cadrul conceptual de bază pentru introducerea unor subiecte mai avansate (și practice) și, de asemenea, pentru a indica conexiunile trecute cu vederea; de exemplu: Diagrame binare de decizie (sunt DFA minimizate; după ce am predat DFA, predau deseori rezolvarea puzzle-urilor bazate pe BDD); scripturi, inclusiv în BioPerl și BioPython (și un cadru excelent în care să consolidați câte meciuri neintenționate pot fi ascunse în regex-urile de script din lumea reală), depanare formală (proprietăți de stare ca FA negate, se intersectează) și chiar VCR sau programare de alarmă pentru intruși la domiciliu (în fiecare zi situația de stres a unui automat slab specificat este predată prin exemple incomplete; poate formalizată utilizând sinteza bazată pe scenariile de joc-în / redare ale Harel a interfețelor utilizator). De asemenea, folosesc setarea pentru a preda Python (aproape) pur subset funcțional, incluzând hărți, lambdas și înțelegeri de seturi, folosind care se pot codifica algoritmi FA standard, adesea într-un mod practic indistinct de definițiile matematice.

Comentarii

• Bun venit, Ganesh!
• Un mod frumos de a preda automatele. Ați fi dispus să vă împărtășiți notele prelegerii?

Au existat cercetări considerabile legate de teoria automatelor în verificarea modelelor utilizate în industrie. Verificați Prelegerile recente ale lui Moshe Vardi la Fields Institute , în special cea de-a treia prelegere „Logică, automate, jocuri și algoritmi” pentru a afla de ce este teoria automatelor încă important și util.

Rezumat:

Abordarea teoretică a automatelor a procedurilor de decizie, introdusă de Buechi, Elgot, Rabin și Trakhtenbrot în anii 1950 și 1960, este una dintre cele mai fundamentale abordări ale procedurilor de decizie. Recent, această abordare a găsit aplicații industriale în verificarea formală a sistemelor hardware și software. Calea de la logică la algoritmi practici merge nu numai prin intermediul automatelor, ci și prin jocuri, ale căror aspecte algoritmice erau studii efectuate de Chandra, Kozen și Stockmeyer la sfârșitul anilor 1970. În această discuție de ansamblu descriem calea de la logică la algoritmi prin automate și jocuri. / div>

Diapozitivele și fișierele audio ale prelegerilor sunt disponibile aici: 1 , 2 , 3 .

Voi arunca un alt răspuns dintr-un unghi practic complet diferit: mașinile cu stare finită (sau cel puțin unele generalizări simple / extensii ale acestora) sunt adesea folosite pe AI partea programării jocului. Se dovedesc a oferi un model excelent pentru încapsularea comportamentului personajului; de exemplu, un inamic ar putea avea state care să reprezinte „patrulare”, „căutare”, „apropiere”, „atac”, „apărare”, „retragere”, „moarte” etc., cu tranziții bine definite între ele. Acest lucru nu implică niciunul dintre aspectele formale ale automatelor, cum ar fi limbajele obișnuite și altele asemenea, dar conceptul automatului este unul foarte important.

Am văzut că limbajul care contrastează teoria și practica, stabilind una peste alta, este chiar desăvârșirea a ignoranței – că demonstrează că un om nu este familiarizat cu primele elemente ale gândirii și merge foarte bine spre a-și demonstra mintea atât de pervertită încât nu poate fi învățată.

– James Mill (scriind pseudonim ca„ PQ”),„ Teorie și practică ”, London and Westminster Review , aprilie 1836

Ar trebui să ținem cont de semantica cuvintelor „practic” și „aplicație”. Pentru unii studenți, practic este orice lucru care îi va ajuta să-și promoveze examenele; pentru alții, orice va veni într-un loc de muncă. În ambele cazuri, Teoria automatelor este foarte practică.

După cum subliniază alții, veți folosi gramaticile, de exemplu, atunci când studiați compilatoarele. Dar chiar mai mult decât atât: înțelegerea întregului concept de a avea stări și reguli diferite pentru tranziții între ele te poate face să fii un programator mai bun atunci când îți dai seama, de exemplu, că codul tău este redundant ici-colo și că, atunci când îl îmbunătățești, aplică în codul dvs. aceleași idei conceptuale în spatele minimizării DFA.

În mod similar pentru „aplicație”. Ce înțelegi prin cuvântul acela? Chiar dacă sunteți un „inginer practic”, veți vedea și folosi idei similare cu cele ale teoriei automatelor în proiecte din lumea reală: cod de programare, diagrame de flux și chiar conceptul simplu, dar strălucit, al unui stack. Pentru nebunii de teorie ca mine, consider aplicațiile ale teoriei automatelor în alte domenii, cum ar fi logica, algebra și teoria modelelor finite. Cu siguranță, probabil că nu va trebui niciodată să folosesc lema de pompare în timp ce fac cumpărături într-un supermarket, dar teoreme de acest gen m-au ajutat să înțeleg structura div> a anumitor clase de limbaje, ca să nu mai vorbim de logica și structurile algebrice cu care sunt în corespondență. Și asta este ceva ce apreciez mai mult decât orice măsură de practic.

Aruncate împreună cu logica, automatele pot oferi modalități de a verificați date cum ar fi

$ \ qquad A \ models \ varphi $

pentru un automat $ A $ și o formulă $ \ varphi $. Dacă $ A $ este un model de sistem și $ \ varphi $ o formalizare a proprietăților dorite, veți obține verificarea sistemului, o preocupare foarte practică cu un număr tot mai mare de aplicații fezabile.

Luând în considerare aspectul automat al lucrurilor duce la algoritmi frumoși. De exemplu, dacă $ \ varphi $ este o formulă LTL și un automat $ A $ a Büchi (adică un automat finit care rulează infinit) puteți traduce $ \ varphi $ la un automat echivalent $ A_ \ varphi $ și verificați dacă $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Automatele finite, adesea scrise despre ele ca mașini cu stări finite în contexte diferite, sau cu variantele lor probabiliste Modelele ascunse Markov pot fi aplicate recunoașterii modelelor și structurii de cuantificare a unui model. De exemplu. care este cea mai mică automată stochastică finită care va genera șiruri în funcție, mai mult sau mai puțin, de o anumită distribuție de probabilitate sau de potrivirea proprietăților statistice ale unui eșantion de șiruri (sau serii de timp) dintr-o anumită distribuție.

A se vedea de exemplu CSSR , un algoritm pentru reconstrucția orbește a stărilor ascunse; este „mai eficient și mai flexibil decât modelele ascunse Markov.

Comentarii

• Pentru a adăuga la partea practică, modelele ascunse Markov sunt utilizate în recunoașterea vorbirii programe precum Kurzweil.

O altă aplicație mai practică a teoriei automatelor este dezvoltarea inteligenței artificiale. Inteligența artificială a fost dezvoltată din conceptul de automat finit. Rețeaua neuronală a roboților este construită pe baza teoriei automatelor. La urma urmei, roboții sunt și automate.

Unii au dat răspunsuri excelente atunci când vine vorba de relația cu industria. Ceea ce ar trebui să fie important este valoarea sa științifică, iar teoria automatelor este adesea poarta de înțelegere a unui nivel superior de teorie a calculului în studiile unui student universitar. Teoria automatelor are un mare set de teoreme care apar peste tot în Informatica teoretică și mai ales atunci când se dorește să se vorbească despre aplicații, cum ar fi compilatoarele. Valoarea sa științifică (nu este învechită, cum ar putea fi? Teoria de bază a domeniului.) Este practică pentru orice om de știință interesat de calcul. Este practică, deoarece este o cunoaștere utilă pentru cei care înțeleg sau doresc pentru a înțelege natura calculului. Dacă nu puteți găsi utilizarea în acesta, pun la îndoială cercetarea celor sau chiar intenția de a studia CS, deoarece nu programează (aceasta este o aplicație a CS), este o știință formală.