Hvor praktisk er Automata Theory? (Norsk)

1. Har du noen gang brukt et verktøy som grep / awk / sed? Regulære uttrykk er hjertet i disse verktøyene.

2. Du vil bli overrasket over hvor mye koding du kan unngå ved prinsipiell bruk av vanlige uttrykk – i «praktiske prosjekter», som en e-post. server.

3. Hvis du er en CS-dur, vil du definitivt skrive en kompilator / tolk for et (minst et lite) språk. Hvis du noen gang har prøvd denne oppgaven før og ble sittende fast, vil du sette pris på hvor mye litt teori (aka kontekstfri grammatikk) kan hjelpe deg. Denne teorien har gjort en en gang umulig oppgave til noe som kan fullføres over en helg. (Og den vant oppfinneren en Turing-pris – google BNF).

4. Hvis du på et eller annet tidspunkt er CS-major, må du lene deg tilbake og tenke på det filosofiske grunnlaget for databehandling, og ikke omtrent hvor kul den neste versjonen av Android API er. På et relatert notat er det universitetets jobb å ikke forberede deg på de neste 5 årene av livet ditt, men å forberede deg på de neste 50. Det eneste de kan gjøre i denne forbindelse er å hjelpe deg å tenke – tenk av automatteori som et av disse kursene.

En av de mer praktiske manifestasjonene av CS er Compiler Construction. I 1965 startet Knuth studien av LR-analysatorer. Raskt (på mindre enn et tiår) hadde vi LALR-parsere som er en delmengde av deterministisk pushdown-automat som lar oss implementere shift / redusere parsers. et bevis (av Knuth) på at «prefikser» av språket viser seg å være vanlige (din endelige automat). Dette er opphavet til automatiserte parsergeneratorer som yacc / bison osv.

Det er trygt å si at programmeringsspråk slik vi kjenner dem skylder mye av deres effektivitet for denne utviklingen.

Her er et annet eksempel: hjertet i TCP / IP-protokollen er en endelig tilstandsmaskin. Hvor mye mer praktisk kan det bli?

Hver seriøs CS-student, spesielt de praktiske, bør ta hensyn til automatteori. Det er grunnlaget for mye av datavitenskapens rikdom.

Kommentarer

• Parsing av kildefiler er egentlig ikke den interessante (og viktige) delen av en kompilator, så jeg gjør ikke ‘ ikke tenke at det er trygt å si at » programmeringsspråk som vi kjenner dem skylder mye av deres kompileringseffektivitet for denne utviklingen «. Videre er det mulig å analysere språk ved hjelp av forskjellige verktøy, for eksempel PEG-er eller parsing-kombinatorer (dvs. parsec).

Kan du høre den støyen ? Det er lyden av tusen strålende teoremer, applikasjoner og verktøy som ler i automatteoretiske himmelen.

Språk og automater er elegante og robuste begreper du finner i alle områder innen informatikk. Språk er ikke tørre, formalistiske hand-me-downs fra databehandling forhistorie.Språkteoriperspektivet distillerer tilsynelatende kompliserte spørsmål om sofistikerte, ugjennomsiktige objekter til enkle utsagn om ord og trær. Formelle språk spiller en rolle i informatikk som ligner det grunnleggende og spillendrende synspunktet som algebra og topologi bringer til klassisk matematikk. Her er noen praktiske, ganske kompliserte, praktiske problemer som blir kontaktet via språkteori.

1. Du vil oppdage duplikatforekomster av en setning i et dokument og slette den andre forekomsten. I hovedsak vil du erstatte en sekvens på et språk.
2. Inneholder et program et påstandsbrudd? Respekterer en enhetsdriver visse protokoller når de kommuniserer med kjernen? Oppførselen til et program er et sett med henrettelser; med andre ord et språk. Korrekthetsegenskapen er et annet språk. Programkorrekthetsproblemet utgjør en kontroll for inkludering av språk.
3. Kan programvaren din sitte fast i en uendelig løkke? Inneholder en distribuert algoritme en livelock? Vi trenger språk over uendelige ord, men visningen om inkludering av språk gjelder fortsatt.
4. Du vil lage et desinfiseringsmiddel for å oppdage ondsinnet Javascript som er lagt inn i et webapplikasjon. Settet med ondsinnede strenger er et språk. Strengsettet kom inn i skjemaene på et annet språk. Du vil bestemme om skjæringspunktet mellom disse språkene ikke er tomt.
5. Driftstidsovervåking av reaktive og oppdragskritiske systemer. Du vil utforme en programvaremonitor som fører tilsyn med kjemiske prosesser, eller spore oppdateringer til en finansiell database. Dette er hjertespråklige inkluderings- og kryssproblemer.
6. Mønstergjenkjenning med sine mange applikasjoner. Du vil oppdage mønstre i genomiske data, i tekst, i en serie feilrapporter. Dette er problemer der vi får ord fra et ukjent språk og må gjette språket. Dette er språkinferensproblemer.
7. Gitt et sett med XML-dokumenter, vil du omforme et skjema som gjelder disse dokumentene. XML-dokumenter kan idealiseres i trær. Et skjema er da en spesifikasjon av et trespråk, og skjemainferensproblemet er et språkinferensproblem over trespråk.
8. Mange applikasjoner krever automatisk aritmetisk resonnement. Anta at vi fikser en logisk teori som Presburger-aritmetikk, der vi har de naturlige tallene, addisjonen og det mindre enn predikatet. En formel med n variabler representerer et sett med n-dimensjonale vektorer. En vektor er en sekvens av sifre og kan kodes som et ord. Et predikat er da et sett med ord; et språk. Logiske operasjoner som sammenhenger, disjunksjon og negasjon blir skjæringspunkt, forening og komplement av språk (eksistensiell kvantifisering er en slags projeksjon).

Reduksjonen antydet ovenfor behandler språk som abstrakte matematiske objekter. For å anvende disse ideene i praksis trenger vi en datastruktur for å representere språk og algoritmer for å manipulere disse datastrukturene.

Skriv inn automata. Automata lar oss redusere spørsmål om abstrakte matematiske objekter som språk til konkrete, algoritmiske spørsmål om merkede grafer. Språk- og automatteori, i tillegg til et vanvittig antall praktiske anvendelser, gir en veldig viktig intellektuell tjeneste. Vi kan tenke på problemer som spenner fra formatering av postnummer til beslutningsprosedyrer for monadisk andreordens logikk i ensartet og ryddig konseptuelt rom. Hvor utrolig er det!

Jeg har ikke sagt noe om logikk og beslutningsprosedyrer. (Ja, de har praktiske anvendelser.) Se Kavehs svar for en autoritativ oversikt.

Kommentarer

• haha, ironien

Som det ble forklart i de andre svarene, er automatalteori viktig begrepsmessig som en enkel beregningsmodell som vi forstår godt, og regulære uttrykk og automater har mange virkelige applikasjoner.

Her er et lite eksempel for moderne forskning som går tilbake til automatteori for å forstå et moderne konsept. I denne artikkelen viser forskere at vanlige språk alle har egenskapstestere: «Vanlige språk kan testes med et konstant antall spørsmål»

Det er ikke bare vaniljeautomater. Du lærer om det grunnleggende (aksepterer tilstander, epsilon-overganger, …) av en (beregning) modell som hjelper til med å resonnere om hva som kan, og enda viktigere hva som ikke kan uttrykkes med noen spørrespråk. Noen interessante resultater inkluderer:

• ja, det berømte resultatet er at Deterministic Endite Automatons gjenkjenner vanlige språk – så nå vet du hva du trenger for å implementere samsvarende uttrykk.
• Pushdown Automata gjenkjenner Kontekstfrie grammatikker – nå har du en ide om hvordan en parser ser ut (eller i det minste en stor klasse av disse).
• treautomater gjenkjenne utsagn over monadisk andreordens logikk – nå har du en ide om hva som skal til for å implementere noen begrensede programmeringsspråk , eller … for eksempel noen utsagn i SQL .

(og selvfølgelig hopper jeg mye over av andre klasser)

I utgangspunktet er det en veldig generell modell. Klassene dine vil sannsynligvis legge vekt på koblingen mellom automat, språk og logikk.

Hvis jeg så på å relatere dette til konkrete «verdslige» verktøy, ville jeg tilbringe en rolig morgen på biblioteket og lese et par deler (AB?) fra Foundations of Databases av Abiteboul & al, og prøver å koble dette tilbake til klassemateriale. Selvfølgelig er det bare en av (mange) måter å lete etter applikasjoner i en automatklasse, og jeg antar ikke at den mest åpenbare – men det er nettopp derfor det er en interessant øvelse.

Som allerede påpekt i forskjellige svar, gir Automata Theory i UG-kurs en det grunnleggende konseptuelle rammeverket for å introdusere mer avanserte (og praktiske) emner, og også for å påpeke oversett sammenhenger; for eksempel: Binære avgjørelsesdiagrammer (de minimeres DFA; etter å ha undervist i DFA lærer jeg ofte BDD-basert puslespillløsning); skripting inkludert i BioPerl og BioPython (og en flott setting for å forsterke hvor mange utilsiktede treff som kan være skjult i reelle skriptreksper), formell feilsøking (oppgi egenskaper som negert FA, kryss), og til og med programmering av alarm eller alarm for hjemmeinntrenger (hver dag stresssituasjon for en dårlig spesifisert automat lært gjennom ufullstendige eksempler; kanskje formalisert ved hjelp av Harels play-in / play-out scenariobasert syntese av brukergrensesnitt). Jeg bruker også innstillingen til å lære Pythons (nesten) rent funksjonell delmengde, inkludert kart, lambdas og settforståelser, ved hjelp av hvilke man kan kode standard FA-algoritmer, ofte på en måte som praktisk talt ikke kan skelnes fra matematiske defns.

Kommentarer

• Velkommen, Ganesh!
• En fin måte å lære automat på. Ville du være villig til å dele forelesningsnotatene dine?

Det har vært betydelig forskning relatert til automatteori i modellkontroll brukt i bransjen. Sjekk Moshe Vardis nylige forelesninger ved Fields Institute , spesielt 3. forelesning «Logikk, automat, spill og algoritmer» for en smakebit av hvorfor automatteori er fremdeles viktig og nyttig.

Sammendrag:

Den automatteoretiske tilnærmingen til beslutningsprosedyrer, introdusert av Buechi, Elgot, Rabin og Trakhtenbrot på 1950- og 1960-tallet er en av de mest grunnleggende tilnærmingene til beslutningsprosedyrer. Nylig har denne tilnærmingen funnet industrielle applikasjoner i formell verifisering av maskinvare- og programvaresystemer. Veien fra logikk til praktiske algoritmer går ikke bare gjennom automata, men også gjennom spill, hvis algoritmiske aspekter var studier av Chandra, Kozen og Stockmeyer på slutten av 1970-tallet. I denne oversiktspraten beskriver vi veien fra logikk til algoritmer via automat og spill.

Lysbildene og lydfilene til forelesningene er tilgjengelige her: 1 , 2 , 3 .

Jeg vil kaste ut et annet svar fra en helt annen praktisk vinkel: endelige tilstandsmaskiner (eller i det minste noen enkle generaliseringer / utvidelser av dem) brukes ofte på AI side av spillprogrammering. De viser seg å gi en utmerket modell for innkapsling av karakteratferd; for eksempel kan en fiende ha stater som representerer «patrulje», «søk», «tilnærming», «angrep», «forsvare», «retrett», «dø» osv. med veldefinerte overganger mellom dem. Dette involverer ikke noen av de formelle aspektene ved automater som vanlige språk og lignende, men automatikkens konsept er veldig viktig.

Vi har sett at språket som kontrasterer teori og praksis, og som setter det ene over det andre, er selve fullførelsen av uvitenhet – at det viser seg at en mann ikke er kjent med de aller første tankelementene, og går en flott vei mot å bevise at hans sinn er så pervers at han ikke er i stand til å bli lært dem.

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

Vi bør ta hensyn til semantikken til ordene «praktisk» og «anvendelse». For noen studenter er praktisk alt som vil hjelpe dem å bestå eksamen; for andre, alt som kommer opp i en jobb. I begge tilfeller er Automata Theory veldig praktisk.

Som andre påpeker, vil du for eksempel bruke grammatikk når du studerer kompilatorer. Men enda mer enn det: å forstå hele konseptet med å ha forskjellige tilstander og regler for overganger mellom dem kan gjøre deg til en bedre programmerer når du for eksempel innser at koden din er overflødig her og der, og at når du forbedrer den, bruker i koden din den samme konseptuelle ideer bak DFA-minimering.

Tilsvarende for «applikasjon». Hva forstår du med det ordet? Selv om du er en «jordnær ingeniør» vil du se og bruke ideer som ligner på Automata Theory i virkelige verdensprosjekter: programmeringskode, flytskjemaer og til og med det enkle, men likevel strålende konseptet med en stabel. For teorinerder som meg vurderer jeg applikasjoner av Automata Theory på andre områder, som logikk, algebra og endelig modellteori. Sikkert vil jeg sannsynligvis aldri trenge å bruke pumpelemmaet mens jeg handler i et supermarked, men slike setninger har hjulpet meg å forstå -strukturen av visse klasser av språk, for ikke å nevne logikk og algebraiske strukturer de samsvarer med. Og det er noe jeg verdsetter mer enn noe mål på praktisk.

Automatisk kastet sammen med logikk kan tilby måter å sjekk statemens som

$ \ qquad A \ models \ varphi $

for en automat $ A $ og en formel $ \ varphi $. Hvis $ A $ er en modell av et system og $ \ varphi $ en formalisering av ønskede egenskaper, får du systembekreftelse, en veldig praktisk bekymring med et økende antall mulige applikasjoner.

Tatt i betraktning den automatiske siden av ting fører til fine algoritmer. For eksempel, hvis $ \ varphi $ er en LTL formel og $ A $ a Büchi automat (dvs. en uendelig kjørende endelig automat) kan du oversette $ \ varphi $ til en tilsvarende automat $ A_ \ varphi $ og sjekk om $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Finite Automata, ofte skrevet om som endelige tilstandsmaskiner i forskjellige sammenhenger, eller med sine sannsynlige varianter Skjulte Markov-modeller kan brukes på mønstergjenkjenning og kvantifiserende struktur av et mønster. F.eks. hva er den minste stokastiske endelige automaten som vil generere strenger, mer eller mindre, til en gitt sannsynlighetsfordeling, eller samsvarende statistiske egenskaper til et utvalg strenger (eller tidsserier) fra en eller annen fordeling.

Se for eksempel CSSR , en algoritme for blind rekonstruksjon av skjulte tilstander; det er mer effektivt og fleksibelt enn skjulte Markov-modeller.

Kommentarer

• For å legge til den praktiske siden, brukes skjulte Markov-modeller i talegjenkjenning programmer som Kurzweil.

En annen mer praktisk anvendelse av automatteori er utviklingen av kunstig intelligens. Kunstig intelligens ble utviklet fra begrepet endelig automat. Det nevrale nettverket av roboter er konstruert på grunnlag av automatteori. Tross alt er også roboter automata.

Noen har gitt gode svar når det gjelder hvordan det forholder seg til industrien. Det som burde være viktig er dens vitenskapelige verdi, og Automata-teorien er ofte døren til å først forstå et høyere nivå av beregningsteori i en studenterstudent. Automata-teorien har et stort sett med teoremer som dukker opp overalt i teoretisk informatikk, og spesielt når man vil snakke om applikasjon som Compilers. Dens vitenskapelige verdi (det er ikke utdatert, hvordan kan det være? Det er kjerneteorien for feltet.) Er praktisk for enhver forsker som er interessert i beregning. Det er praktisk da det er kunnskap som er nyttig for de som forstår eller ønsker for å forstå arten av beregning. Hvis du ikke finner bruk i den, stiller jeg spørsmål ved forskning eller til og med intensjon om å studere CS, da den ikke programmerer (det er en applikasjon av CS), den er en formell vitenskap.