Mennyire praktikus az automata elmélet?

1. Olyan eszközt használtál már, mint a grep / awk / sed? A rendszeres kifejezések alkotják ezeknek az eszközöknek a lényegét.

2. Meg fog lepődni azon, hogy mennyi kódolást tud elkerülni a rendszeres kifejezések elvi használata – “gyakorlati projektekben”, például egy e-mailben szerver.

3. Ha CS-szakos vagy, akkor mindenképpen fordítót / tolmácsot fogsz írni egy (legalább egy kicsi) nyelvhez. Ha valaha is megpróbáltad Ezt a feladatot korábban elakadtam, és elakadtál, értékelni fogod, hogy egy kis elmélet (más néven kontextusmentes nyelvtanok) mennyire tudnak segíteni neked. Ez az elmélet egy egyszer lehetetlenné vált feladattá változtatta azt a dolgot, amely egy hétvégén elvégezhető. (És megnyerte a feltalálót Turing-díj – google BNF).

4. Ha CS-szakos vagy, akkor valamikor le kell dőlned és gondolkodnod kell a számítás filozófiai alapjain, és nem arról, hogy az Android API következő verziója mennyire klassz. Ezzel kapcsolatban az egyetem feladata, hogy ne felkészítse életének következő 5 évére, hanem felkészítse a következő 50 évre. Az egyetlen dolog, amit tehetnek ebben a tekintetben, az, hogy segítsen gondolkodni – gondolkodni az automaták elméletének egyik tanfolyama.

Az egyik gyakorlati megnyilvánulás a CS a fordítószerkezet. 1965-ben Knuth megkezdte az LR parserek tanulmányozását. Gyorsan (kevesebb, mint egy évtized alatt) rendelkezésünkre álltak a LALR elemzők, amelyek a determinisztikus lehúzható automaták részhalmazai, amelyek lehetővé teszik számunkra a váltás / csökkentés elemzés végrehajtását.

A LALR elemzés megvalósíthatóságának és hatékonyságának középpontjában az áll. annak bizonyítása (Knuth által), hogy a nyelv “előtagjai” szabályosnak bizonyulnak (a véges automatád). Ez az automatikus elemző generátorok, például a yacc / bison stb. Genezise.

Nyugodtan mondhatjuk, hogy a programozási nyelvek, amint ismerjük őket, fordítási hatékonyságuk nagy részét ezeknek a fejlesztéseknek köszönhetik.

Itt van egy másik példa: a TCP / IP protokoll szíve egy véges állapotú gép. Mennyivel praktikusabb lehet?

Minden komolyabb CS hallgatónak, különösen a gyakorlati hallgatóknak, figyelniük kell az automaták elméletére. Ez az alapja a számítástechnika gazdagságának.

Megjegyzések

• A forrásfájlok elemzése nem igazán a fordító érdekes (és fontos) része, ezért nem ‘ nem gondolja, hogy nyugodtan kijelenthető, hogy a ” programozási nyelvek, mivel ismerjük őket, fordítási hatékonyságuk nagy részét ezeknek a fejlesztéseknek köszönhetik. “. Ezenkívül lehetséges a nyelvek elemzése különböző eszközökkel, például PEG-ek vagy elemző kombinátorok (pl. Parsec) használatával.

Hallja ezt a zajt ? Ez ezer ragyogó tétel, alkalmazás és eszköz hangja az automata-elméleti mennyországban.

A nyelvek és az automaták elegáns és robusztus fogalmak, amelyeket a számítástechnika minden területén megtalál. A nyelvek nem szárazak, az őstörténet kiszámításával kapcsolatos formalista kéz-hátrányok.A nyelvelméleti perspektíva a kifinomult, átláthatatlan tárgyakkal kapcsolatos bonyolultnak tűnő kérdéseket egyszerű szavakká és fákra bontja. A hivatalos nyelvek az informatikában szerepet játszanak, hasonlóan az algebra és a topológia által a klasszikus matematikához juttatott alapvető és játékváltoztató nézőponthoz. Íme néhány gyakorlati, meglehetősen bonyolult, gyakorlati probléma, amelyet a nyelvelmélet segítségével közelítenek meg.

1. Meg akarja találni a kifejezésben előforduló ismétlődő kifejezéseket, és törölni kívánja a második előfordulást. Lényegében egy szekvenciát szeretne helyettesíteni egy nyelvben.
2. Tartalmaz egy program állítássértést? Tiszteletben tartja-e az eszközillesztő bizonyos protokollokat, amikor interakcióba lépnek a kernellel? A program viselkedése végrehajtások összessége; más szóval egy nyelv. A helyesség tulajdonság egy másik nyelv. A program helyességével kapcsolatos probléma a nyelv befogadásának ellenőrzését jelenti.
3. Lehet-e beragadni a szoftverét egy végtelen ciklusba? Tartalmaz egy elosztott algoritmus megélhetést? Nyelvekre van szükségünk a végtelen szavakkal szemben, de a nyelv felvételi nézete továbbra is érvényes.
4. Fertőtlenítőt szeretne létrehozni egy webalkalmazásba bevitt rosszindulatú Javascript felderítésére. A rosszindulatú karakterláncok halmaza egy nyelv. A húrkészlet egy másik nyelven került az űrlapokba. Meg szeretné tudni, hogy ezeknek a nyelveknek a kereszteződése nem üres-e.
5. A reaktív és a misszió szempontjából kritikus rendszerek futásidejű figyelése. Tervezni kíván egy szoftverfigyelőt, amely felügyeli a vegyi folyamat működését, vagy nyomon követi a pénzügyi adatbázis frissítéseit. Ezek középpontjában a nyelv befogadásának és metszéspontjának problémái állnak.
6. A mintafelismerés számos alkalmazásával. Kimutatni szeretné a genomikus adatok, a szöveg és a hibajelentések sorozatát. Ezek olyan problémák, amikor ismeretlen nyelvből kapunk szavakat, és nekünk kell kitalálnunk a nyelvet. Ezek nyelvi következtetési problémák.
7. XML-dokumentumok együttesével meg akarja változtatni az ezekre a dokumentumokra vonatkozó sémát. Az XML dokumentumok idealizálhatók egy fán. A séma ekkor a fa nyelvének specifikációja, a séma következtetési problémája pedig a fa nyelveivel szembeni nyelv következtetési problémája.
8. Sok alkalmazás automatizált számtani indoklást igényel. Tegyük fel, hogy rögzítünk egy olyan logikai elméletet, mint például a Presburger-aritmetika, amelyben megadjuk a természetes számokat, összeadást és a predikátumnál kevesebbet. Az n változóval rendelkező képlet n-dimenziós vektorok halmazát jelenti. A vektor számjegyek sorozata, és szóként kódolható. Az állítmány ekkor szavak halmaza; egy nyelv. Az olyan logikai műveletek, mint a kötőszó, a diszjunkció és a tagadás, a nyelvek metszéspontjává, egyesülésévé és kiegészítésévé válnak (az egzisztenciális számszerűsítés egyfajta vetület).

A fentebb utalt redukció a nyelveket elvont matematikai objektumként kezeli. Ezen ötletek gyakorlati alkalmazásához szükségünk van egy adatszerkezetre, amely a nyelveket ábrázolja, és algoritmusokra, amelyek manipulálják ezeket az adatstruktúrákat.

Adja meg az automatákat. Az automaták lehetővé teszik számunkra, hogy az absztrakt matematikai objektumokkal, például nyelvekkel kapcsolatos kérdéseket konkrét, algoritmikus kérdésekké redukáljuk a címkézett grafikonokkal kapcsolatban. A nyelvek és az automaták elmélete az őrületes számú gyakorlati alkalmazás mellett nagyon jelentős szellemi szolgáltatást nyújt. Gondolhatunk olyan problémákra, mint az irányítószámok formázása és a monád másodrendű logika döntési eljárásai az egységes és zavartalan fogalmi térben. Milyen csodálatos!

Semmit sem mondtam a logikáról és a döntési eljárásokról. (Igen, vannak gyakorlati alkalmazásuk.) Tekintse át Kaveh válaszát a mérvadó áttekintéshez.

Megjegyzések

• haha, az irónia

Amint azt a többi válasz is kifejtette, az automaták elmélete fogalmilag fontos, mint egyszerű számítási modell, amelyet jól megértünk, és a reguláris kifejezéseknek és az automatáknak számos valós alkalmazásuk van. Ebben a tanulmányban a kutatók bebizonyítják, hogy a szokásos nyelveknek mindegyikük rendelkezik tesztelővel: “A rendszeres nyelvek állandó számú lekérdezéssel tesztelhetők”

Ez nem csak vanília automaták. Megismered egy (számítási) alapjait (állapotok elfogadása, epsilon-átmenetek, …). modell, amely segít megindokolni, hogy mit lehet, és ami még fontosabb, mit nem lehet kifejezni egyes lekérdezési nyelvekkel. Néhány érdekes eredmény:

• igen, a híres eredmény az, hogy A determinisztikus véges automaták felismerik a szokásos nyelveket – így most már tudod amire szükséged van a reguláris kifejezésillesztés megvalósításához.
• Ledugható automaták felismerik a kontextus nélküli nyelvtanokat – most már megvan ötlet arról, hogy néz ki egy elemző (vagy legalábbis ezek nagy csoportja).
• fa automaták felismeri a utasításokat monád másodrendű logika felett – most már van ötlete arról, hogy mit kell tennie néhány kényszer programozási nyelv megvalósításához , vagy … például néhány utasítás az SQL-ben .

(és természetesen sokat “kihagyok” osztályokból)

Alapvetően nagyon általános modell. Az óráid valószínűleg hangsúlyozni fogják az automaták, a nyelvek és a logika közötti kapcsolatot.

Ha ezt konkrét “világi” eszközökhöz kapcsolódóan néztem, akkor egy nyugodt délelőttöt töltöttem volna a könyvtárban, elolvasva pár részt (AB?) a következőtől: Az adatbázisok alapjai , írta Abiteboul & al, és megpróbálta ezt visszacsatolni az osztály anyagához. Természetesen csak az egyik (sok) módja az automaták osztályának alkalmazásainak keresésére, és azt hiszem, nem a legnyilvánvalóbb -, de éppen ezért érdekes gyakorlat.

Amint azt a különféle válaszok már rámutattak, az UG tanfolyamok Automata elmélete az egyik alapvető fogalmi keretet nyújtja a fejlettebb (és gyakorlati) témák bevezetéséhez, valamint figyelmen kívül hagyott kapcsolatok rámutatására; például: bináris döntési diagramok (ezek minimalizálják a DFA-t; a DFA tanítása után gyakran tanítok BDD alapú puzzle megoldást); szkriptek, beleértve a BioPerl és a BioPython programokat (és nagyszerű beállítások, amelyek megerősítik, hogy hány nem kívánt meccs rejtőzhet a valós szkriptek regexps-jeiben), formális hibakeresés (állapot tulajdonságok, mint elutasított FA, metszéspont), sőt, videomagnó vagy otthoni behatoló riasztás programozása (egy rosszul meghatározott automata napi stresszhelyzete hiányos példákon keresztül tanítva; esetleg Harel lejátszási / lejátszási szcenárió alapú felhasználói felületének szintézisével formalizálva.) A beállítást a Python (majdnem) tisztán tanítására is felhasználom. funkcionális részhalmaz, beleértve a térképeket, a lambdákat és a megértéseket, amelyek segítségével kódolni lehet a szokásos FA algoritmusokat, gyakran gyakorlatilag megkülönböztethetetlenül a matematikai defnektől.

Megjegyzések

• Üdvözlünk, Ganesh!
• Az automaták tanításának szép módja. Hajlandó lenne megosztani az előadás jegyzeteit?

Jelentős kutatások történtek az automaták elméletével kapcsolatban az iparban alkalmazott modellellenőrzésben. Ellenőrizze Moshe Vardi legutóbbi előadásait a Fields Institute-ban , különös tekintettel a “Logika, automaták, játékok és algoritmusok” 3. előadásra, hogy ízelítőt adjon az automatika-elmélet miértjéről továbbra is fontos és hasznos.

Kivonat:

A döntési eljárások automata-elméleti megközelítése, amelyet Buechi, Elgot, Rabin és A Trakhtenbrot az 1950-es és 1960-as években az egyik legalapvetőbb megközelítés a döntési eljárásokhoz. A közelmúltban ez a megközelítés ipari alkalmazásokat talált a hardver és szoftver rendszerek hivatalos ellenőrzésében. A logikától a gyakorlati algoritmusokig vezető út nemcsak automatákon, hanem játékok révén, amelyek algoritmikus szempontjait Chandra, Kozen és Stockmeyer tanulmányozták az 1970-es évek végén. Ebben az áttekintő előadásban leírjuk az utat a logikától az algoritmusokig automatákon és játékokon keresztül.

Az előadások diái és hangfájljai itt érhetők el: 1 , 2 , 3 .

Egy másik választ teljesen más gyakorlati szempontból dobok ki: az AI-n gyakran használnak véges állapotú gépeket (vagy legalább néhány egyszerű általánosítást / kiterjesztést). a játék programozásának oldala. Kiderül, hogy kiváló modellt nyújtanak a karakter viselkedésének beágyazására; például egy ellenségnek lehetnek olyan államai, amelyek “járőrözést”, “keresést”, “megközelítést”, “támadást”, “védekezést”, “visszavonulást”, “meghalást” stb. képviselnek, jól körülhatárolt átmenetekkel. Ez nem foglalja magában az automaták olyan formai vonatkozásait, mint a normál nyelvek és hasonlók, de az automata koncepció nagyon lényeges.

Láttuk, hogy az a nyelv, amely az elméletet és a gyakorlatot szembeállítja, az egyiket a másik fölé állítva, maga a kiteljesedés tudatlanság – hogy bebizonyítja, hogy az ember nem ismeri a gondolkodás legelső elemeit, és nagyszerű utat mutat be annak bizonyítására, hogy elméje annyira elferdült, hogy képtelen tanítani őket.

– James Mill (álnéven írja:„ PQ”),„ Elmélet és gyakorlat ”, London and Westminster Review , 1836. április

Figyelembe kell vennünk a “gyakorlati” és az “alkalmazás” szavak szemantikáját. Néhány hallgató számára a praktikus minden olyan, ami segít a vizsgákon; mások számára bármi, ami felmerül egy munkában. Mindkét esetben az Automata elmélet valóban nagyon praktikus.

Amint mások hangsúlyozzák, a fordítók tanulmányozása során például nyelvtanokat fog használni. De még ennél is több: a különböző állapotok és a köztük lévő átmenetek szabályainak teljes koncepciójának megértése jobb programozóvá teheti Önt, amikor például rájön, hogy a kódja itt-ott felesleges, és ha javítja, akkor alkalmazzák t a kódodban ugyanazok a koncepcionális ötletek a DFA minimalizálása mögött.

Hasonlóan az “alkalmazáshoz”. Mit értesz ezzel a szóval? Még akkor is, ha “földhözragadt mérnök” vagy, a valós projektekben meglátod és felhasználod az Automata Theory elképzeléseihez hasonló ötleteket: programozási kódot, folyamatábrákat és még a verem egyszerű, ámde zseniális koncepcióját is. A hozzám hasonló elméleti majmok számára az Automataelmélet alkalmazásait más területeken, például a logika, az algebra és a véges modellelmélet szempontjából tekintem. Bizonyára soha nem lesz szükségem a szivattyúzási lemma használatára szupermarketben vásárlás közben, de az ehhez hasonló tételek segítettek megérteni a szerkezetet , nem beszélve azokról a logikákról és algebrai struktúrákról, amelyekkel összhangban vannak. És ez az, amit a gyakorlatiasság minden mértékénél jobban értékelek.

A logikával együtt dobva az automaták módot kínálnak ellenőrizze az olyan állampolgárokat, mint

$ \ qquad A \ models \ varphi $

egy $ A $ automatához és egy $ \ varphi $ képlethez. Ha a $ A $ egy rendszer modellje, a $ \ varphi $ pedig a kívánt tulajdonságok formalizálása, akkor rendszerellenőrzést kap, ez nagyon praktikus probléma a növekvő számú megvalósítható alkalmazással.

Figyelembe véve a dolgok automatizálási oldalát szép algoritmusokhoz vezet. Például, ha a $ \ varphi $ egy LTL képlet és $ A $ egy Büchi automata (azaz egy végtelenül futó véges automata), akkor lefordíthatja a $ \ varphi $ egy egyenértékű $ A_ \ varphi $ automatához, és ellenőrizze, hogy $ $ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Véges automaták, amelyekről gyakran véges állapotú gépként írnak, különböző összefüggésekben, vagy valószínűségi változataikkal a Rejtett Markov-modellek alkalmazhatók a minta felismerésére és a minta számszerűsítésére. Például. mi a legkisebb sztochasztikus véges automatika, amely többé-kevésbé az adott valószínűség-eloszlásnak megfelelő sztringeket generál, vagy valamely eloszlásból származó húrok (vagy idősorok) mintájának statisztikai tulajdonságait illeszti össze.

Lásd például a CSSR algoritmust a rejtett állapotok vak rekonstrukciójára; hatékonyabb és rugalmasabb, mint a Rejtett Markov modellek.

Megjegyzések

• A gyakorlati oldal kiegészítéséhez a Rejtett Markov modelleket használják a beszédfelismerésben. olyan programok, mint a Kurzweil.

Az automaták elméletének egy másik praktikusabb alkalmazása a mesterséges intelligencia fejlesztése. A mesterséges intelligenciát a véges automata koncepciójából fejlesztették ki. A robotok neurális hálózatát az automata elmélet alapján építik fel. Végül is a robotok is automaták.

Vannak, akik nagyszerű válaszokat adtak, amikor az iparhoz viszonyul. Fontosnak kell lennie annak tudományos értékének, és az automaták elmélete gyakran az a lehetőség, hogy először megértsük a számítási elmélet magasabb szintjét egyetemi hallgató tanulmányaiban. Az automaták elméletének számos tétele van, amelyek az Elméleti Számítástudományban mindenhol felbukkannak, és különösen, ha valaki olyan alkalmazásokról akar beszélni, mint például a Compilers. Tudományos értéke (nem elavult, hogyan lehetne? Ez a terület alapvető elmélete.) Minden tudós számára praktikus, aki érdeklődik a számítás iránt. Praktikus, mivel a tudás hasznos azok számára, akik értenek vagy szeretnének megérteni a számítás természetét. Ha nem találja meg benne a felhasználást, megkérdőjelezem a kutatókat, vagy akár szándékomban áll tanulmányozni a CS-t, mivel ez nem programozás (ez a CS alkalmazása), ez a formális tudomány.