Jak praktická je teorie automatů?

1. Už jste někdy používali nástroj jako grep / awk / sed? Srdce těchto nástrojů tvoří regulární výrazy.

2. Budete překvapeni, kolik kódování se můžete vyhnout principiálním používáním regulárních výrazů – v „praktických projektech“, jako je e-mail server.

3. Pokud jste CS major, určitě budete psát překladač / tlumočník pro (alespoň malý) jazyk. Pokud jste někdy zkoušeli tento úkol dříve a zasekl se, oceníte, jak vám může trochu teorie (aka bezkontextových gramatik) pomoci. Tato teorie udělala z kdysi nemožného úkolu něco, co lze dokončit za víkend. (A vyhrálo vynálezce ocenění Turing – google BNF).

4. Pokud jste CS major, musíte se v určitém okamžiku posadit a přemýšlet o filozofických základech práce s počítačem, a ne o tom, jak skvělá je další verze Android API. Související poznámkou je, že úkolem univerzity není připravit vás na příštích 5 let vašeho života, ale připravit vás na příštích 50. Jediné, co v tomto ohledu mohou udělat, je pomoci vám myslet – myslet teorie automatů jako jeden z těchto kurzů.

Jeden z praktičtějších projevů CS je konstrukce kompilátoru. V roce 1965 zahájil Knuth studium analyzátorů LR. Rychle (za méně než deset let) jsme měli analyzátory LALR, které jsou podmnožinou deterministických pushdown automatů, které nám umožňují implementovat analyzátory posunu / redukce.

Jádrem proveditelnosti a účinnosti analýzy LALR je důkaz (podle Knutha), že „předpony“ jazyka se ukáží jako pravidelné (váš konečný automat). Toto je geneze automatických generátorů syntaktických analyzátorů, jako jsou yacc / bison atd.

Dá se říci, že programovací jazyky, jak je známe, vděčí tomuto vývoji za velkou efektivitu kompilace.

Zde je další příklad: srdcem protokolu TCP / IP je stroj s konečným stavem. O kolik je to praktičtější?

Každý vážný student CS, zejména praktický, by měl věnovat pozornost teorii automatů. Je základem velké části bohatství počítačové vědy.

Komentáře

• Analýza zdrojových souborů není ve skutečnosti zajímavou (a důležitou) částí kompilátoru, takže ‚ nemyslí si, že lze s jistotou říci, že “ programovací jazyky, jak je známe, vděčí tomuto vývoji za velkou část své efektivity kompilace „. Kromě toho je možné analyzovat jazyky pomocí různých nástrojů, například PEG nebo kombinačních analyzátorů (tj. Parsec).

Slyšíte ten šum ? Je to zvuk tisíce brilantních vět, aplikací a nástrojů smějících se v automaticko-teoretickém nebi.

Jazyky a automaty jsou elegantní a robustní koncepty, které najdete ve všech oblastech počítačové vědy. Jazyky nejsou suché, formalistické hand-me-downy z výpočetní prehistorie.Perspektiva jazykové teorie destiluje zdánlivě komplikované otázky o sofistikovaných neprůhledných objektech do jednoduchých výroků o slovech a stromech. Formální jazyky hrají v informatice roli podobnou základnímu a měnícímu se pohledu, který algebře a topologii přináší klasická matematika. Zde je několik praktických, poměrně komplikovaných a praktických problémů, ke kterým se přistupuje prostřednictvím teorie jazyků.

1. Chcete zjistit duplicitní výskyty fráze v dokumentu a odstranit druhý výskyt. V podstatě chcete nahradit sekvenci v jazyce.
2. Obsahuje program porušení tvrzení? Respektuje ovladač zařízení při komunikaci s jádrem určité protokoly? Chování programu je sada poprav; jinými slovy jazyk. Vlastnost správnosti je jiný jazyk. Problém správnosti programu se rovná kontrole zařazení jazyka.
3. Může váš software uvíznout v nekonečné smyčce? Obsahuje distribuovaný algoritmus živý zámek? Potřebujeme jazyky nad nekonečnými slovy, ale stále platí pohled na zařazení jazyka.
4. Chcete vytvořit dezinfekční prostředek pro detekci škodlivého skriptu Javascript zadaného do webové aplikace. Sada škodlivých řetězců je jazyk. Sada řetězců zadaných do formulářů v jiném jazyce. Chcete zjistit, zda průnik těchto jazyků není prázdný.
5. Sledování běhu reaktivních a kritických systémů za běhu. Chcete navrhnout softwarový monitor, který bude dohlížet na provoz vašeho chemického procesu, nebo sledovat aktualizace finanční databáze. Jedná se o problémy se začleněním a průnikem jazyka.
6. Rozpoznávání vzorů s mnoha aplikacemi. Chcete detekovat vzory v genomových datech, v textu, v sérii hlášení o chybách. Jedná se o problémy, kdy dostáváme slova z neznámého jazyka a musíme jazyk uhádnout. Jedná se o problémy s odvozením jazyka.
7. Vzhledem k sadě dokumentů XML chcete zpětně analyzovat schéma, které se na tyto dokumenty vztahuje. Dokumenty XML lze idealizovat jako stromy. Schéma je pak specifikací stromového jazyka a problém odvození schématu je problémem odvození jazyka ve stromových jazycích.
8. Mnoho aplikací vyžaduje automatické aritmetické uvažování. Předpokládejme, že opravíme logickou teorii, jako je Presburgerova aritmetika, ve které máme přirozená čísla, sčítání a predikát méně než. Vzorec s n proměnnými představuje sadu n-rozměrných vektorů. Vektor je sekvence číslic a lze jej kódovat jako slovo. Predikát je pak sada slov; jazyk. Logické operace, jako je konjunkce, disjunkce a negace, se stávají průnikem, sjednocením a doplňkem jazyků (existenční kvantifikace je druh projekce).

Redukce naznačená výše považuje jazyky za abstraktní matematické objekty. Abychom tyto myšlenky mohli uplatnit v praxi, potřebujeme datovou strukturu, která představuje jazyky a algoritmy pro manipulaci s těmito datovými strukturami.

Zadejte automaty. Automaty nám umožňují redukovat otázky týkající se abstraktních matematických objektů, jako jsou jazyky, na konkrétní, algoritmické otázky týkající se označených grafů. Jazyky a teorie automatů, kromě šíleného množství praktických aplikací, poskytují velmi významnou intelektuální službu. Můžeme přemýšlet o problémech od formátování PSČ až po rozhodovací postupy pro monadickou logiku druhého řádu v jednotném a přehledném koncepčním prostoru. To je úžasné!

Neřekl jsem nic o logice a rozhodovacích postupech. (Ano, mají praktické aplikace.) Autoritativní přehled najdete v odpovědi Kaveha.

Komentáře

• haha, ironie

Jak bylo vysvětleno v ostatních odpovědích, teorie automatů je důležitá koncepčně jako jednoduchý výpočetní model, kterému dobře rozumíme, a regulární výrazy a automaty mají mnoho aplikací v reálném životě.

Zde je malý příklad moderního výzkumu, který se vrací k teorii automatů, aby pochopil moderní koncept. V tomto článku vědci dokazují, že všechny běžné jazyky mají testery vlastností: „Pravidelné jazyky lze testovat s konstantním počtem dotazů“

Nejedná se pouze o vanilkové automaty. Učíte se o základech (přijímání stavů, epsilon-přechody, …) a (výpočetní) model, který pomáhá při uvažování o tom, co může, a co je důležitější, co nelze vyjádřit pomocí některých dotazovacích jazyků. Mezi zajímavé výsledky patří:

• ano, známým výsledkem je, že deterministické konečné automaty rozpoznávají běžné jazyky – takže teď víte co potřebujete k implementaci shody regulárních výrazů.
• Pushdown Automata rozpoznávají bezkontextové gramatiky – nyní máte představu o tom, jak vypadá analyzátor (nebo alespoň jejich velká třída).
• stromové automaty rozpoznávat příkazy nad monadickou logikou druhého řádu – nyní máte představu o tom, co je potřeba k implementaci některých programovacích jazyků omezení , nebo … například některé příkazy v SQL .

(a samozřejmě hodně přeskakuji) jiných tříd)

Je to v zásadě velmi obecný model. Vaše kurzy pravděpodobně zdůrazní vazbu mezi automaty, jazyky a logikou.

Kdybych se díval na to, že to souvisí s konkrétními „světskými“ nástroji, strávil bych pohodové dopoledne v knihovně a přečetl jsem si několik částí (AB?) z Základy databází od Abiteboul & al a pokus o připojení zpět k materiálu třídy. Samozřejmě je to jen jeden z (mnoha) způsobů hledání aplikací třídy automatů a myslím, že není nejviditelnější – ale právě proto je to zajímavé cvičení.

Jak již bylo uvedeno v různých odpovědích, teorie automatů v kurzech UG poskytuje základní koncepční rámec pro zavádění pokročilejších (a praktických) témat a také za poukázání na přehlédnuté souvislosti; například: Binární rozhodovací diagramy (jsou to minimalizované DFA; po výuce DFA často učím řešení hádanek na základě BDD); skriptování včetně BioPerl a BioPython (a skvělé prostředí, ve kterém lze posílit, kolik neúmyslných shod může být skryto v regexps skriptů v reálném světě), formální ladění (vlastnosti stavu jako negovaný FA, protínají se) a dokonce i programování alarmu videorekordéru nebo domácího vetřelce (každodenní stresová situace špatně specifikovaného automatu učená na neúplných příkladech; možná formalizovaná pomocí Harelovy scénáře play-in / play-out založené na uživatelských rozhraních). Toto nastavení používám také k výuce Pythonu (téměř) čistě funkční podmnožina, včetně map, lambd a porozumění množinám, pomocí nichž lze kódovat standardní algoritmy FA, často způsobem, který je prakticky nerozeznatelný od matematických definic.

Komentáře

• Vítejte, Ganesh!
• Pěkný způsob výuky automatů. Byli byste ochotni se podělit o své poznámky z přednášky?

V oblasti teorie automatů proběhl značný výzkum při kontrole modelů používaných v průmyslu. Podívejte se na nedávné přednášky Moshe Vardi na Fields Institute , zejména 3. přednášku „Logika, automaty, hry a algoritmy“, abyste zjistili, proč je teorie automatů stále důležité a užitečné.

Abstrakt:

Teoretický přístup automatů k rozhodovacím postupům, který zavedli Buechi, Elgot, Rabin a Trakhtenbrot v 50. a 60. letech je jedním z nejzákladnějších přístupů k rozhodovacím postupům. V poslední době tento přístup našel průmyslové aplikace při formálním ověřování hardwarových a softwarových systémů. Cesta od logiky k praktickým algoritmům prochází nejen automaty, ale také prostřednictvím her, jejichž algoritmickými aspekty byly studie Chandry, Kozena a Stockmeyera na konci 70. let. V tomto přehledovém rozhovoru popisujeme cestu od logiky k algoritmům prostřednictvím automatů a her.

Prezentace a zvukové soubory přednášek jsou k dispozici zde: 1 , 2 , 3 .

Vyhodím další odpověď ze zcela jiného praktického úhlu: na AI se často používají konečné stavové automaty (nebo alespoň některé jejich jednoduché zobecnění / rozšíření). strana programování her. Ukázalo se, že poskytují vynikající model pro zapouzdření chování postav; například nepřítel může mít státy představující „hlídku“, „hledání“, „přiblížení“, „útok“, „obranu“, „ústup“, „smrt“ atd. s dobře definovanými přechody mezi nimi. To nezahrnuje žádné formální aspekty automatů, jako jsou běžné jazyky apod., Ale koncept automatu je velmi základní.

Viděli jsme, že jazyk, který kontrastuje s teorií a praxí a nastavuje jeden nad druhým, je velmi završením nevědomosti – že prokazuje, že člověk není seznámen s úplně prvními myšlenkovými prvky, a jde skvělým způsobem, jak dokázat, že jeho mysl je tak zvrácená, že se jí nedokáže naučit.

– James Mill (pseudonymně psal jako„ PQ”),“ Theory and Practice ”, London and Westminster Review , duben 1836

Měli bychom vzít v úvahu sémantiku slov „praktický“ a „aplikace“. Pro některé studenty je praktické cokoli, co jim pomůže složit zkoušky; pro ostatní cokoli, co se v práci objeví. V obou případech je teorie automatů opravdu velmi praktická.

Jak zdůrazňují jiní, při studiu překladačů budete používat například gramatiky. Ale ještě víc: porozumění celé koncepci různých stavů a pravidel pro přechody mezi nimi vás může udělat lepším programátorem, když si například uvědomíte, že váš kód je sem a tam nadbytečný a že když ho vylepšíte, používají ve vašem kódu stejné koncepční nápady za minimalizací DFA.

Podobně pro „aplikaci“. Co rozumíš tomu slovu? I když jste „pozemský inženýr“, uvidíte a použijete nápady podobné těm z teorie automatů v projektech reálného světa: programovací kód, vývojové diagramy a dokonce i jednoduchý, ale brilantní koncept zásobníku. U teoretiků, jako jsem já, považuji aplikace teorie automatů v jiných oblastech, jako je logika, algebra a teorie konečných modelů. Určitě nikdy nebudu muset použít čerpací lemma při nakupování v supermarketu, ale takové věty mi pomohly pochopit strukturu určitých tříd jazyků, nemluvě o logických a algebraických strukturách, s nimiž korespondují. A to je něco, co si cením víc než jakákoli míra praktičnosti.

Společně s logikou mohou automaty nabídnout způsoby, jak zkontrolujte statemeny jako

$ \ qquad A \ models \ varphi $

pro automat $ A $ a vzorec $ \ varphi $. Pokud $ A $ je model systému a $ \ varphi $ je formalizace požadovaných vlastností, získáte ověření systému, což je velmi praktický problém s rostoucím počtem proveditelných aplikací.

S ohledem na automatickou stránku věci vede k pěkným algoritmům. Například pokud $ \ varphi $ je LTL vzorec a $ A $ a Büchi automat (tj. Nekonečně běžící konečný automat), můžete přeložit $ \ varphi $ ekvivalentnímu automatu $ A_ \ varphi $ a zkontrolujte, zda $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Konečné automaty, o nichž se často píše jako o strojích s konečným stavem v různých kontextech, nebo s jejich pravděpodobnostními variantami. Skryté Markovovy modely lze použít k rozpoznávání vzorů a kvantifikaci struktury vzoru. Např. jaké jsou nejmenší stochastické konečné automaty, které budou generovat řetězce podle víceméně podle daného rozdělení pravděpodobnosti nebo odpovídající statistické vlastnosti vzorku řetězců (nebo časových řad) z nějaké distribuce.

Viz například CSSR , algoritmus pro slepou rekonstrukci skrytých stavů; je efektivnější a flexibilnější než Skryté Markovovy modely.

Komentáře

• Chcete-li přidat praktickou stránku, Skryté Markovovy modely se používají v rozpoznávání řeči programy jako Kurzweil.

Další praktičtější aplikací teorie automatů je vývoj umělé inteligence. Umělá inteligence byla vyvinuta z konceptu konečného automatu. Neuronová síť robotů je konstruována na základě teorie automatů. Nakonec jsou roboty také automaty.

Někteří poskytli skvělé odpovědi, pokud jde o vztah k průmyslu. Důležitá by měla být jeho vědecká hodnota a teorie automatů je často branou k pochopení vyšší úrovně teorie výpočtu. ve vysokoškolském studiu. Teorie automatů má velkou sadu vět, které se v Teoretické informatice objevují všude, zvláště když chcete hovořit o aplikacích, jako jsou překladače. Jeho vědecká hodnota (není zastaralá, jak by to mohlo být? Jde o základní teorii oboru) je praktická pro každého vědce, který se zajímá o výpočty. Je praktická, protože jde o znalosti užitečné pro ty, kteří rozumí nebo chtějí pochopit podstatu výpočtu. Pokud v něm nemůžete najít uplatnění, zpochybňuji výzkum nebo dokonce záměr studovat CS, protože to není programování (to je aplikace CS), je to formální věda.