Hvor praktisk er Automata Theory?

1. Har du nogensinde brugt et værktøj som grep / awk / sed? Regulære udtryk udgør kernen i disse værktøjer.

2. Du vil blive overrasket over, hvor meget kodning du kan undgå ved principiel brug af regelmæssige udtryk – i “praktiske projekter”, som en e-mail server.

3. Hvis du er “CS-major”, vil du helt sikkert skrive en compiler / tolk til et (i det mindste et lille) sprog. Hvis du nogensinde har prøvet denne opgave før og sidder fast, vil du forstå, hvor meget en lille teori (alias kontekstfri grammatik) kan hjælpe dig. Denne teori har gjort en en gang umulig opgave til noget, der kan afsluttes i løbet af en weekend. (Og den vandt opfinderen en Turing-pris – google BNF).

4. Hvis du på et eller andet tidspunkt er CS-major, er du nødt til at læne dig tilbage og tænke på det filosofiske fundament for computing og ikke næsten hvor cool den næste version af Android API er. På en lignende note er det universitetets opgave ikke at forberede dig til de næste 5 år af dit liv, men at forberede dig på de næste 50. Det eneste de kan gøre i denne henseende er at hjælpe dig med at tænke – tænk af automatteori som et af disse kurser.

En af de mere praktiske manifestationer af CS er Compiler Construction. I 1965 startede Knuth undersøgelsen af LR-parsere. Hurtigt (på mindre end et årti) havde vi LALR-parsere, som er en delmængde af deterministisk pushdown-automata, der giver os mulighed for at implementere shift / reducere parsers.

Kernen i gennemførligheden og effektiviteten af LALR-parsing er et bevis (af Knuth) for, at “prefikser” af sproget viser sig at være regelmæssige (din endelige automat). Dette er oprindelsen af automatiserede parsergeneratorer som yacc / bison osv.

Det er sikkert at sige, at programmeringssprog, som vi kender dem, skylder meget af deres kompilerende effektivitet til denne udvikling.

Her er et andet eksempel: hjertet i TCP / IP-protokollen er en finite state-maskine. Hvor meget mere praktisk kan det få?

Enhver seriøs CS-studerende, især de praktiske, skal være opmærksom på automatteori. Det er grundlaget for meget af informatikens rigdom.

Kommentarer

• Parsing af kildefiler er ikke rigtig den interessante (og vigtige) del af en compiler, så jeg don ‘ tænker ikke, at det er sikkert at sige, at ” programmeringssprog, som vi kender dem, skylder meget af deres kompilerende effektivitet til denne udvikling “. Desuden er det muligt at parse sprog ved hjælp af forskellige værktøjer, for eksempel PEGer eller parsingkombinatorer (dvs. parsec).

Kan du høre den støj ? Det er lyden af tusind strålende sætninger, applikationer og værktøjer, der griner i automatteoretisk himmel.

Sprog og automater er elegante og robuste begreber, som du finder inden for alle områder inden for datalogi. Sprog er ikke tørre, formalistiske hand-me-downs fra computing forhistorie.Sprogteoretisk perspektiv destillerer tilsyneladende komplicerede spørgsmål om sofistikerede, uigennemsigtige objekter i enkle udsagn om ord og træer. Formelle sprog spiller en rolle inden for datalogi svarende til det grundlæggende og spilændrende synspunkt, som algebra og topologi bringer til klassisk matematik. Her er nogle praktiske, ret komplicerede, praktiske problemer, der tilgås via sprogteori.

1. Du vil få øje på dobbelte forekomster af en sætning i et dokument og slette den anden forekomst. I det væsentlige vil du erstatte en sekvens på et sprog.
2. Indeholder et program en påstandsovertrædelse? Respekterer en enhedsdriver visse protokoller, når de interagerer med kernen? Et programs opførsel er et sæt henrettelser; med andre ord et sprog. Korrekthedsegenskaben er et andet sprog. Programmets korrekthedsproblem udgør en kontrol af sproginddragelse.
3. Kan din software sidde fast i en uendelig løkke? Indeholder en distribueret algoritme en livelock? Vi har brug for sprog over uendelige ord, men visningen af sproginddragelse gælder stadig.
4. Du vil oprette et desinfektionsmiddel til at opdage ondsindet Javascript, der er indtastet i en webapplikation. Sættet med ondsindede strenge er et sprog. Sættet med strenge indtastet formularerne på et andet sprog. Du vil afgøre, om skæringspunktet mellem disse sprog ikke er tomt.
5. Kørselstidsovervågning af reaktive og missionskritiske systemer. Du ønsker at designe en softwaremonitor, der fører tilsyn med driften af din kemiske proces eller spore opdateringer til en finansiel database. Disse er kerneproblemer med sproginddragelse og skæringsproblemer.
6. Mønstergenkendelse med sine mange anvendelser. Du vil opdage mønstre i genomiske data i tekst i en række fejlrapporter. Dette er problemer, hvor vi får ord fra et ukendt sprog og skal gætte sproget. Dette er sproginferensproblemer.
7. Givet et sæt XML-dokumenter, vil du omvende et skema, der gælder for disse dokumenter. XML-dokumenter kan idealiseres i træer. Et skema er derefter en specifikation af et træsprog, og skemainferensproblemet er et sproginferensproblem over træsprog.
8. Mange applikationer kræver automatisk aritmetisk ræsonnement. Antag, at vi retter en logisk teori som f.eks. Presburger-aritmetik, hvor vi har de naturlige tal, tilføjelse og mindre end prædikatet. En formel med n variabler repræsenterer et sæt n-dimensionelle vektorer. En vektor er en sekvens af cifre og kan kodes som et ord. Et prædikat er derefter et sæt ord; et sprog. Logiske operationer som sammenhæng, disjunktion og negation bliver skæringspunkt, forening og komplement af sprog (eksistentiel kvantificering er en slags projektion).

Den reduktion, der antydes ovenfor, behandler sprog som abstrakte matematiske objekter. For at anvende disse ideer i praksis har vi brug for en datastruktur til at repræsentere sprog og algoritmer til at manipulere disse datastrukturer.

Indtast automaten. Automatisk giver os mulighed for at reducere spørgsmål om abstrakte matematiske objekter som sprog til konkrete, algoritmiske spørgsmål om mærkede grafer. Sprog og automatteori udover et vanvittigt antal praktiske anvendelser giver en meget vigtig intellektuel service. Vi kan tænke på problemer lige fra formatering af postnumre til beslutningsprocedurer for monadisk andenordenslogik i ensartet og ryddeligt konceptuelt rum. Hvor forbløffende er det!

Jeg har ikke sagt noget om logik og beslutningsprocedurer. (Ja, de har praktiske anvendelser.) Se Kavehs svar for en autoritativ oversigt.

Kommentarer

• haha, ironien

Som det blev forklaret i de andre svar, er automatiteori vigtig begrebsmæssigt som en simpel beregningsmodel, som vi forstår godt, og regulære udtryk og automater har mange virkelige applikationer.

Her er et lille eksempel til moderne forskning, der går tilbage til automatteori for at forstå et moderne koncept. I denne artikel viser forskere, at almindelige sprog alle har egenskabstestere: “Regelmæssige sprog kan testes med et konstant antal forespørgsler”

Det er ikke bare vaniljeautomater. Du lærer om de grundlæggende (accepterende tilstande, epsilon-overgange, …) af en (beregningsmæssig) model, der hjælper med at ræsonnere om, hvad der kan, og vigtigere, hvad der ikke kan udtrykkes med nogle forespørgselssprog. Et par interessante resultater inkluderer:

• ja, det berømte resultat er, at Deterministic Finite Automatons genkender almindelige sprog – så nu ved du det hvad du har brug for til at implementere regulært udtryk.
• Pushdown Automata genkender Kontekstfrie grammatikker – nu har du en idé om, hvordan en parser ser ud (eller i det mindste en stor klasse af dem).
• træautomater genkende udsagn over monadisk andenordens logik – nu har du en idé om, hvad der kræves for at implementere nogle begrænsede programmeringssprog , eller … for eksempel nogle udsagn i SQL .

(og selvfølgelig springer jeg meget over af andre klasser)

Dybest set er det en meget generel model. Dine klasser vil sandsynligvis understrege forbindelsen mellem automat, sprog og logik.

Hvis jeg så på at relatere dette til konkrete “verdslige” værktøjer, tilbragte jeg en afslappet morgen på biblioteket med at læse et par dele (AB?) fra Fundament of Databases af Abiteboul & al, og forsøger at forbinde dette tilbage til klassemateriale. Naturligvis er det bare en af de (mange) måder at lede efter applikationer af en automatklasse, og jeg tror ikke den mest åbenlyse – men det er netop derfor, det er en interessant øvelse.

Som allerede påpeget i forskellige svar, giver Automata Theory i UG-kurser en den grundlæggende konceptuelle ramme til introduktion af mere avancerede (og praktiske) emner og også til at påpege oversete forbindelser; for eksempel: Binære beslutningsdiagrammer (de minimeres DFA; efter undervisning i DFA underviser jeg ofte i BDD-baseret puslespil); scripting inklusive i BioPerl og BioPython (og en fantastisk indstilling, hvor man kan forstærke, hvor mange utilsigtede kampe, der kan være skjult i reelle script-regexps), formel fejlfinding (tilstandsegenskaber som negeret FA, skærer hinanden) og endda programmering af VCR eller hjemmeindbrudere (hver dag stresssituation for en dårligt specificeret automat undervist gennem ufuldstændige eksempler; måske formaliseret ved hjælp af Harels play-in / play-out scenariebaseret syntese af brugergrænseflader). Jeg bruger også indstillingen til at lære Pythons (næsten) rent funktionel delmængde, herunder kort, lambdas og sætforståelser, ved hjælp af hvilke man kan kode standard FA-algoritmer, ofte på en måde, der praktisk talt ikke kan skelnes fra matematiske defns.

Kommentarer

• Velkommen, Ganesh!
• En dejlig måde at undervise i automater på. Ville du være villig til at dele dine forelæsningsnotater?

Der har været betydelig forskning relateret til automatteori i modelkontrol, der anvendes i branchen. Tjek Moshe Vardis seneste foredrag på Fields Institute , især den 3. forelæsning “Logik, automatik, spil og algoritmer” for en smag af, hvorfor automatteori er stadig vigtig og nyttig.

Sammendrag:

Den automatteoretiske tilgang til beslutningsprocedurer, introduceret af Buechi, Elgot, Rabin og Trakhtenbrot i 1950erne og 1960erne er en af de mest grundlæggende tilgange til beslutningsprocedurer. For nylig har denne tilgang fundet industrielle applikationer i formel verifikation af hardware og softwaresystemer. Vejen fra logik til praktiske algoritmer går ikke kun gennem automater, men også gennem spil, hvis algoritmiske aspekter var undersøgelser foretaget af Chandra, Kozen og Stockmeyer i slutningen af 1970erne. I denne oversigtsforedrag beskriver vi stien fra logik til algoritmer via automater og spil.

Slides og lydfiler fra forelæsninger er tilgængelige her: 1 , 2 , 3 .

Jeg vil smide et andet svar ud fra en helt anden praktisk vinkel: endelige tilstandsmaskiner (eller i det mindste nogle enkle generaliseringer / udvidelser af dem) bruges ofte til AI side af spilprogrammering. De viser sig at give en fremragende model til indkapsling af karakteradfærd; for eksempel kan en fjende have stater, der repræsenterer “patrulje”, “søgning”, “tilgang”, “angreb”, “forsvare”, “tilbagetog”, “dø” osv. med veldefinerede overgange mellem dem. Dette involverer ikke nogen af de formelle aspekter af automater som almindelige sprog og lignende, men automatens koncept er meget kernen.

Vi har set, at sproget, der står i kontrast til teori og praksis, der sætter det ene over det andet, er selve fuldendelsen af uvidenhed – at det viser, at et menneske ikke er bekendt med de allerførste elementer i tanken og går meget i retning af at bevise, at hans sind er så pervers, at han ikke er i stand til at blive undervist dem.

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

Vi skal tage højde for semantikken i ordene “praktisk” og “anvendelse”. For nogle studerende er praktisk alt, hvad der hjælper dem med at bestå deres eksamen; for andre, alt, hvad der kommer op i et job. I begge tilfælde er Automata Theory meget praktisk.

Som andre påpeger, vil du f.eks. Bruge grammatikker, når du studerer kompilatorer. Men endnu mere end det: At forstå hele konceptet med at have forskellige tilstande og regler for overgange mellem dem kan gøre dig til en bedre programmør, når du for eksempel indser, at din kode er overflødig her og der, og at når du forbedrer den, anvender i din kode det samme konceptuelle ideer bag DFA-minimering.

Tilsvarende for “applikation”. Hvad forstår du med det ord? Selvom du er en “jordnær ingeniør”, vil du se og bruge ideer, der ligner dem fra Automata Theory i virkelige verdensprojekter: programmeringskode, flowdiagrammer og endda det enkle, men strålende koncept med en stak. For teoretiske nørder som mig overvejer jeg anvendelser af Automata Theory inden for andre områder, som logik, algebra og endelig modelteori. Sikkert vil jeg sandsynligvis aldrig have brug for pumpelemmaet, mens jeg handler i et supermarked, men sådanne sætninger har hjulpet mig med at forstå struktur af visse sprogklasser, for ikke at nævne de logik- og algebraikstrukturer, de er i overensstemmelse med. Og det er noget, som jeg værdsætter mere end noget mål for praktisk brug.

Automatisk kastet sammen med logik kan tilbyde måder at tjek statemens som

$ \ qquad A \ models \ varphi $

for en automat $ A $ og en formel $ \ varphi $. Hvis $ A $ er en model af et system og $ \ varphi $ en formalisering af ønskede egenskaber, får du systembekræftelse, et meget praktisk problem med et stigende antal gennemførlige applikationer.

I betragtning af den automatiske side af tingene fører til gode algoritmer. For eksempel, hvis $ \ varphi $ er en LTL formel og $ A $ a Büchi automat (dvs. en uendeligt kørende endelig automat), kan du oversætte $ \ varphi $ til en tilsvarende automat $ A_ \ varphi $ og tjek om $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Finite Automata, ofte skrevet om som finite state-maskiner i forskellige sammenhænge eller med deres sandsynlige varianter Skjulte Markov-modeller kan anvendes til mønstergenkendelse og kvantificering af et mønsters struktur. For eksempel. hvad er den mindste stokastiske, endelige automat, der genererer strenge mere eller mindre efter en given sandsynlighedsfordeling eller matchende statistiske egenskaber for en prøve af strenge (eller tidsserier) fra en vis fordeling.

Se for eksempel CSSR , en algoritme til blind rekonstruktion af skjulte tilstande; det er mere effektivt og fleksibelt end skjulte Markov-modeller.

Kommentarer

• For at føje til den praktiske side bruges skjulte Markov-modeller til talegenkendelse programmer som Kurzweil.

En anden mere praktisk anvendelse af automatteori er udviklingen af kunstig intelligens. Kunstig intelligens blev udviklet ud fra begrebet finite automaton. Det neurale netværk af robotter er konstrueret på baggrund af automatateori. Når alt kommer til alt er robotter også automatiske.

Nogle har givet gode svar, når det kommer til, hvordan det relaterer sig til industrien. Hvad der skal være vigtigt er dets videnskabelige værdi, og Automata-teorien er ofte døren til først at forstå et højere niveau af beregningsteori i en studerendes studium. Automata-teorien har et stort sæt sætninger, der dukker op overalt i teoretisk datalogi, og især når man vil tale om anvendelse såsom Compilers. Dens videnskabelige værdi (det er ikke forældet, hvordan kunne det være? Det er kerneteorien for marken.) Er praktisk for enhver forsker, der er interesseret i beregning. Det er praktisk, da det er viden, der er nyttig for dem, der forstår eller ønsker at forstå arten af beregning. Hvis du ikke kan finde brug i det, sætter jeg spørgsmålstegn ved forskningen eller endda hensigten om at studere CS, da det ikke programmerer (det er en anvendelse af CS), det er en formel videnskab.