Hur praktisk är Automata Theory?

1. Har du någonsin använt ett verktyg som grep / awk / sed? Regulära uttryck utgör kärnan i dessa verktyg.

2. Du kommer bli förvånad över hur mycket kodning du kan undvika genom principiell användning av reguljära uttryck – i ”praktiska projekt”, som ett e-postmeddelande server.

3. Om du är CS-major skriver du definitivt en kompilator / tolk för ett (åtminstone ett litet) språk. Om du någonsin har provat den här uppgiften innan och fastnade, kommer du att uppskatta hur mycket lite teori (aka kontextfria grammatik) kan hjälpa dig. Denna teori har gjort en en gång omöjlig uppgift till något som kan slutföras under en helg. (Och den vann uppfinnaren en Turing-utmärkelse – google BNF).

4. Om du någon gång är CS-major måste du luta dig tillbaka och tänka på de filosofiska grunderna för datorer, och inte bara hur cool nästa version av Android API är. På en relaterad anteckning är det universitetets uppgift att inte förbereda dig för de kommande fem åren av ditt liv, utan att förbereda dig för de kommande 50. Det enda de kan göra i detta avseende är att hjälpa dig att tänka – tänk av automatisk teori som en av dessa kurser.

En av de mer praktiska manifestationerna av CS är Compiler Construction. 1965 inledde Knuth studien av LR-analysatorer. Vi hade snabbt (på mindre än ett decennium) LALR-parsers som är en delmängd av deterministisk pushdown-automat som gör det möjligt för oss att implementera shift / reducera parsers.

Kärnan i genomförbarheten och effektiviteten med LALR-parsing är ett bevis (av Knuth) på att ”prefix” av språket visar sig vara vanligt (din ändliga automat). Detta är uppkomsten av automatiserade parsergeneratorer som yacc / bison etc.

Det är säkert att säga att programmeringsspråk, som vi känner dem, har mycket av sin sammanställningseffektivitet för denna utveckling.

Här är ett annat exempel: kärnan i TCP / IP-protokollet är en slutlig maskin. Hur mycket mer praktiskt kan det få?

Varje seriös CS-student, särskilt de praktiska, bör vara uppmärksam på automatteorin. Det är grunden för mycket av datavetenskapens rikedom.

Kommentarer

• Att analysera källfiler är egentligen inte den intressanta (och viktiga) delen av en kompilator, så jag gör inte ’ tänker att det är säkert att säga att ” programmeringsspråk som vi känner till dem är mycket skyldiga att sammanställa effektiviteten för denna utveckling ”. Dessutom är det möjligt att analysera språk med hjälp av olika verktyg, till exempel PEG eller parsingkombinatorer (dvs. parsec).

Kan du höra det bullret ? Det är ljudet av tusen lysande satser, applikationer och verktyg som skrattar i automatteoretiska himlen.

Språk och automatik är eleganta och robusta begrepp som du hittar inom alla områden inom datavetenskap. Språken är inte torra, formalistiska hand-me-downs från datorhistoria.Språkteorins perspektiv destillerar till synes komplicerade frågor om sofistikerade, ogenomskinliga objekt i enkla uttalanden om ord och träd. Formella språk spelar en roll inom datavetenskap som liknar den grundläggande och spelförändrande synpunkten som algebra och topologi tillför klassisk matematik. Här är några praktiska, ganska komplicerade, praktiska problem som tas upp via språkteori.

1. Du vill upptäcka dubbletter av en fras i ett dokument och radera den andra förekomsten. I huvudsak vill du ersätta en sekvens på ett språk.
2. Innehåller ett program ett påståendebrott? Respekterar en enhetsdrivrutin vissa protokoll när de interagerar med kärnan? Ett programs beteende är en uppsättning avrättningar; med andra ord ett språk. Korrekthetsegenskapen är ett annat språk. Programmets korrekthetsproblem motsvarar en kontroll av språkinklusion.
3. Kan din programvara fastna i en oändlig slinga? Innehåller en distribuerad algoritm en livelock? Vi behöver språk över oändliga ord, men vyn för språkinlämning gäller fortfarande.
4. Du vill bygga en sanitizer för att upptäcka skadlig Javascript som har skrivits in i en webbapplikation. Uppsättningen av skadliga strängar är ett språk. Uppsättningen strängar angav formuläret på ett annat språk. Du vill avgöra om skärningspunkten mellan dessa språk inte är tom.
5. Driftstidsövervakning av reaktiva och uppdragskritiska system. Du vill utforma en programvarumonitor som övervakar driften av din kemiska process eller spårar uppdateringar till en ekonomisk databas. Dessa är språkinklusionsproblem och korsningsproblem.
6. Mönsterigenkänning med dess många applikationer. Du vill upptäcka mönster i genomdata, i text, i en serie felrapporter. Det här är problem där vi får ord från ett okänt språk och måste gissa språket. Dessa är språkinferensproblem.
7. Med en uppsättning XML-dokument vill du omvandla ett schema som gäller för dessa dokument. XML-dokument kan idealiseras i träd. Ett schema är då en specifikation av ett trädspråk och schemanslutningsproblem är ett språkinferensproblem över trädspråk.
8. Många applikationer kräver automatiserat aritmetiskt resonemang. Anta att vi fixar en logisk teori som Presburger-aritmetik, där vi har de naturliga siffrorna, additionen och det mindre än predikatet. En formel med n variabler representerar en uppsättning n-dimensionella vektorer. En vektor är en sekvens av siffror och kan kodas som ett ord. Ett predikat är då en uppsättning ord; ett språk. Logiska operationer som konjunktion, disjunktion och negation blir skärningspunkt, union och komplement av språk (existentiell kvantifiering är en slags projektion).

Den minskning som antyds ovan behandlar språk som abstrakta matematiska objekt. För att tillämpa dessa idéer i praktiken behöver vi en datastruktur för att representera språk och algoritmer för att manipulera dessa datastrukturer.

Ange automaten. Automaten låter oss reducera frågor om abstrakta matematiska objekt som språk till konkreta, algoritmiska frågor om märkta grafer. Språk och automatteori, förutom ett vansinnigt antal praktiska tillämpningar, ger en mycket betydelsefull intellektuell tjänst. Vi kan tänka på problem som sträcker sig från att formatera postnummer till beslutsprocedurer för monadisk andra ordningslogik i enhetligt och snyggt konceptutrymme. Hur fantastiskt är det!

Jag har inte sagt något om logik och beslutsprocedurer. (Ja, de har praktiska tillämpningar.) Se Kavehs svar för en auktoritativ översikt.

Kommentarer

• haha, ironin

Som förklarades i de andra svaren är automatiska teorier viktigt begreppsmässigt som en enkel beräkningsmodell som vi förstår väl, och reguljära uttryck och automatar har många verkliga applikationer.

Här är ett litet exempel för modern forskning som går tillbaka till automatteori för att förstå ett modernt koncept. I denna uppsats bevisar forskare att vanliga språk alla har egenskapstestare: ”Vanliga språk kan testas med ett konstant antal frågor”

Det är inte bara vaniljautomater. Du lär dig mer om grunderna (accepterar tillstånd, epsilon-övergångar, …) för en (beräknings) modell som hjälper till att resonera om vad som kan och ännu viktigare vad som inte kan uttryckas med vissa frågespråk. Några intressanta resultat inkluderar:

• ja, det berömda resultatet är att Deterministic Finite Automatons känner igen vanliga språk – så nu vet du vad du behöver för att implementera matchning av reguljära uttryck.
• Pushdown Automata känner igen Kontextfria grammatik – nu har du en uppfattning om hur en analysator ser ut (eller åtminstone en stor klass av dessa).
• trädautomater känna igen uttalanden över monadisk andra ordens logik – nu har du en uppfattning om vad som krävs för att implementera några begränsade programmeringsspråk , eller … till exempel några uttalanden i SQL .

(och jag hoppas naturligtvis mycket av andra klasser)

I grund och botten är det en mycket allmän modell. Dina klasser kommer troligen att betona kopplingen mellan automat, språk och logik.

Om jag tittade på att relatera detta till konkreta ”världsliga” verktyg skulle jag tillbringa en lugn morgon på biblioteket och läsa ett par delar (AB?) från Foundations of Databases av Abiteboul & al, och försöker koppla detta tillbaka till klassmaterialet. Naturligtvis är det bara ett av de (många) sätten att leta efter applikationer i en automatklass, och jag antar inte att det är mest uppenbart – men det är just därför det är en intressant övning.

Som redan påpekats i olika svar ger Automata Theory i UG-kurser en grundläggande konceptuell ram för att introducera mer avancerade (och praktiska) ämnen, och även för att påpeka förbises förbindelser; till exempel: Binära beslutsdiagram (de minimeras DFA; efter att ha undervisat i DFA undervisar jag ofta på BDD-baserade pussellösning); skript inklusive i BioPerl och BioPython (och en fantastisk inställning för att förstärka hur många oavsiktliga matchningar som kan vara dolda i verkliga skriptrexps), formell felsökning (ange egenskaper som förnekad FA, korsning) och till och med programmering av VCR eller heminbrottslarm (varje dag stresssituation för en dåligt specificerad automat som lärs ut genom ofullständiga exempel; kanske formaliserad med Harels ”play-in / play-out” scenariobaserad syntes av användargränssnitt). Jag använder också inställningen för att lära Pythons (nästan) rent funktionell delmängd, inklusive kartor, lambdas och inställningsförståelser, med vilka man kan koda standard FA-algoritmer, ofta på ett sätt som praktiskt taget inte kan skiljas från matematiska defns.

Kommentarer

• Välkommen, Ganesh!
• Ett trevligt sätt att lära automatisera. Skulle du vara villig att dela dina föreläsningsanteckningar?

Det har gjorts betydande forskning relaterad till automatteori i modellkontroll som används i branschen. Kontrollera Moshe Vardis senaste föreläsningar vid Fields Institute , särskilt den tredje föreläsningen ”Logik, automat, spel och algoritmer” för en smak av varför automatteori är fortfarande viktigt och användbart.

Sammanfattning:

Den automatteoretiska inställningen till beslutsprocedurer, introducerad av Buechi, Elgot, Rabin och Trakhtenbrot på 1950- och 1960-talet är ett av de mest grundläggande tillvägagångssätten för beslutsprocedurer. Nyligen har detta tillvägagångssätt hittat industriella applikationer i formell verifiering av hårdvara och mjukvarusystem. Vägen från logik till praktiska algoritmer går inte bara genom automat, utan också genom spel, vars algoritmiska aspekter var studier av Chandra, Kozen och Stockmeyer i slutet av 1970-talet. I det här översiktsföredraget beskriver vi vägen från logik till algoritmer via automatar och spel.

Presentationerna och ljudfilerna finns här: 1 , 2 , 3 .

Jag kastar ett annat svar från en helt annan praktisk vinkel: slutliga tillståndsmaskiner (eller åtminstone några enkla generaliseringar / förlängningar av dem) används ofta på AI sidan av spelprogrammeringen. De visar sig vara en utmärkt modell för inkapsling av karaktärsbeteende; till exempel kan en fiende ha stater som representerar ”patrull”, ”sökning”, ”tillvägagångssätt”, ”attack”, ”försvara”, ”reträtt”, ”dö”, etc. med väldefinierade övergångar mellan dem. Detta involverar inte några av de formella aspekterna av automatik som vanliga språk och liknande, men automatens -koncept är mycket grundläggande.

Vi har sett att språket som står i kontrast till teori och praktik, som sätter det ovanför varandra, är själva fulländningen av okunnighet – att det bevisar att en man inte känner till de allra första tankelementen och går en bra väg mot att bevisa att hans sinne är så pervers att han inte kan lära dem.

– James Mill (skriver pseudonymt som” PQ”),“ Theory and Practice ”, London and Westminster Review , april 1836

Vi bör ta hänsyn till semantiken för orden ”praktisk” och ”tillämpning”. För vissa studenter är praktiskt allt som hjälper dem att klara sina tentor; för andra, allt som kommer upp i ett jobb. I båda fallen är Automata Theory verkligen praktiskt.

Som andra påpekar kommer du att använda grammatik, till exempel när du studerar kompilatorer. Men ännu mer än det: att förstå hela konceptet att ha olika tillstånd och regler för övergångar mellan dem kan göra dig till en bättre programmerare när du till exempel inser att din kod är överflödig här och där, och att när du förbättrar den, tillämpar i din kod samma konceptuella idéer bakom DFA-minimering.

På samma sätt för ”applikation”. Vad förstår du med det ordet? Även om du är en ”jordnär ingenjör” kommer du att se och använda idéer som liknar de i Automata Theory i verkliga projekt: programmeringskod, flödesdiagram och till och med det enkla men ändå lysande konceptet med en stack. För teorinördar som jag överväger jag tillämpningar av Automata Theory inom andra områden, som logik, algebra och ändlig modellteori. Visst kommer jag förmodligen aldrig att behöva använda pumpningslemma när jag handlar i en stormarknad, men sådana satser har hjälpt mig att förstå -strukturen av vissa klasser av språk, för att inte tala om logik- och algebraikstrukturerna de överensstämmer med. Och det är något som jag värdesätter mer än något praktiskt mått.

Automaten kan kastas tillsammans med logik, kolla statemens som

$ \ qquad A \ models \ varphi $

för en automat $ A $ och en formel $ \ varphi $. Om $ A $ är en modell av ett system och $ \ varphi $ en formalisering av önskade egenskaper får du systemverifiering, ett mycket praktiskt problem med ett växande antal genomförbara applikationer.

Med tanke på automatiska sidan av saker leder till fina algoritmer. Till exempel, om $ \ varphi $ är en LTL -formel och $ A $ a Büchi-automat (dvs. en oändligt körande ändlig automat) kan du översätta $ \ varphi $ till en motsvarande automat $ A_ \ varphi $ och kontrollera om $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Finite Automata, ofta skrivet om som finite state-maskiner i olika sammanhang, eller med sina probabilistiska varianter Dolda Markov-modeller kan användas för mönsterigenkänning och kvantifieringsstruktur för ett mönster. T.ex. vad är den minsta stokastiska ändliga automaten som genererar strängar, mer eller mindre, till en given sannolikhetsfördelning, eller matchande statistiska egenskaper för ett strängprov (eller tidsserie) från någon fördelning.

Se till exempel CSSR , en algoritm för blind rekonstruktion av dolda tillstånd; det är effektivare och mer flexibelt än Hidden Markov-modeller.

Kommentarer

• För att lägga till den praktiska sidan används Hidden Markov-modeller i taligenkänning program som Kurzweil.

En annan mer praktisk tillämpning av automatteori är utvecklingen av artificiell intelligens. Artificiell intelligens utvecklades utifrån begreppet finite automaton. Det neurala nätverket av robotar är konstruerat på grundval av automatiteori. När allt kommer omkring är robotar också automatiska.

Vissa har gett bra svar när det gäller hur det relaterar till industrin. Vad som borde vara viktigt är dess vetenskapliga värde, och Automata-teorin är ofta dörren för att först förstå ett högre nivå av beräkningsteori i en grundstudents studier. Automata-teorin har en stor uppsättning satser som dyker upp överallt inom teoretisk datavetenskap, och särskilt när man vill prata om applikationer som Compilers. Dess vetenskapliga värde (det är inte föråldrat, hur kan det vara? Det är kärnteorin för fältet.) Är praktiskt för alla forskare som är intresserade av beräkning. Det är praktiskt eftersom det är kunskap som är användbar för dem som förstår eller vill ha för att förstå beräkningens karaktär. Om du inte hittar användning i det ifrågasätter jag forskning eller ens avsikt att studera CS eftersom det inte programmerar (det är en tillämpning av CS), det är en formell vetenskap.