Kuinka käytännöllinen on automaatioteoria?

1. Oletko koskaan käyttänyt työkalua kuten grep / awk / sed? Säännölliset lausekkeet muodostavat näiden työkalujen ytimen.

2. Yllätyt, kuinka paljon koodausta voit välttää käyttämällä säännöllisiä lausekkeita periaatteellisesti – ”käytännön projekteissa”, kuten sähköpostissa. palvelin.

3. Jos olet CS-duuri, kirjoitat varmasti kääntäjän / tulkin (ainakin pienelle) kielelle. Jos olet koskaan yrittänyt tämä tehtävä aiemmin ja juuttui, arvostat kuinka paljon pieni teoria (eli kontekstivapaat kieliopit) voivat auttaa sinua. Tämä teoria on tehnyt kerran mahdottomasta tehtävästä jotain, joka voidaan suorittaa viikonloppuna. (Ja se voitti keksijän Turingin palkinto – google BNF).

4. Jos olet CS-pääaine, sinun täytyy jossain vaiheessa istua alas ja ajatella tietojenkäsittelyn filosofisia perusteita eikä vain siitä, kuinka siisti Android-sovellusliittymän seuraava versio on. Tähän liittyvään seikkaan yliopiston tehtävä ei ole valmistaa sinua seuraavaksi 5 vuodeksi elämästäsi, vaan valmistaa sinut seuraavaan 50 vuoteen. Ainoa asia, jonka he voivat tehdä tässä asiassa, on auttaa sinua ajattelemaan – ajattelemaan automaatiteorian yhtenä näistä kursseista.

Yksi käytännön ilmentymistä CS on Compiler Construction. Vuonna 1965 Knuth aloitti LR-jäsenten tutkimuksen. Nopeasti (alle vuosikymmenessä) meillä oli LALR-jäsentimiä, jotka ovat determinististen pudotusautomaatioiden osajoukko, jonka avulla voimme toteuttaa muutos- / vähennysjäsentäjiä.

LALR-jäsentämisen toteutettavuuden ja tehokkuuden ytimessä on todiste (Knuthilta), että kielen ”etuliitteet” osoittautuvat säännöllisiksi (äärellinen automaatti). Tämä on automaattisten jäsenningeneraattoreiden, kuten yacc / bison jne., Perusta.

Tässä on toinen esimerkki: TCP / IP-protokollan ydin on rajallinen tilakone. Kuinka paljon käytännöllisempää se voi saada?

Jokaisen vakavan CS-opiskelijan, erityisesti käytännön opiskelijoiden, tulisi kiinnittää huomiota automaatioteoriaan. Se on perusta suurelle osalle tietojenkäsittelytieteen rikkautta.

kommentit

• Lähdetiedostojen jäsentäminen ei ole oikeastaan kääntäjän mielenkiintoinen (ja tärkeä) osa, joten en halua ’ ei usko, että on turvallista sanoa, että ” ohjelmointikielet sellaisena kuin ne tunnemme, ovat kiitollisia suuresta osasta kokoamisen tehokkuuttaan näille tapahtumille

Kuuletko melun ? Se on tuhannen loistavan lauseen, sovelluksen ja työkalun ääni nauraen automaatiteoreettisessa taivaassa.

Kielet ja automaatit ovat tyylikkäitä ja vankkoja käsitteitä, jotka löydät kaikilta tietojenkäsittelytieteen osa-alueilta. Kielet eivät ole kuivia, formalistisia haittoja esihistorian laskemisesta.Kieliteorianäkökulma tislaa näennäisesti monimutkaisia kysymyksiä kehittyneistä, läpinäkymättömistä esineistä yksinkertaisiksi lausunnoiksi sanoista ja puista. Muodollisilla kielillä on tietotekniikassa rooli, joka muistuttaa algebran ja topologian klassiseen matematiikkaan tuomaa perustavaa ja muuttuvaa näkökulmaa. Tässä on joitain käytännöllisiä, melko monimutkaisia, käytännön ongelmia, joihin lähestytään kieliteoriaa.

1. Haluat havaita lausekkeen kaksoiskappaleet dokumentissa ja poistaa toisen esiintymän. Pohjimmiltaan haluat korvata jonon kielellä.
2. Sisältääkö ohjelma väitteiden rikkomuksen? Kunnioittaako laiteohjain tiettyjä protokollia ollessaan vuorovaikutuksessa ytimen kanssa? Ohjelman käyttäytyminen on joukko teloituksia; toisin sanoen kieli. Oikeusominaisuus on toinen kieli. Ohjelman oikeellisuusongelma tarkoittaa kielen osallisuuden tarkistusta.
3. Voiko ohjelmisto jumittua äärettömään silmukkaan? Sisältääkö hajautettu algoritmi eläkettä? Tarvitsemme kieliä loputtomien sanojen yli, mutta kielen sisällyttämisnäkymä on edelleen voimassa.
4. Haluat rakentaa puhdistusaineen verkkosovellukseen syötetyn haitallisen Javascriptin havaitsemiseksi. Haitallisten merkkijonojen joukko on kieli. Jousisarja syötettiin lomakkeisiin toisella kielellä. Haluat selvittää, onko näiden kielten risteys tyhjä.
5. Reaktiivisten ja tehtäväkriittisten järjestelmien ajonaikainen seuranta. Haluat suunnitella ohjelmistomonitorin, joka valvoo kemiallisen prosessisi toimintaa, tai seurata rahoitustietokannan päivityksiä. Nämä ovat sydämen kielen osallisuutta ja leikkausongelmia.
6. Kuvion tunnistus lukuisilla sovelluksillaan. Haluat havaita kuviot genomisista tiedoista, tekstistä, virheraporttisarjasta. Nämä ovat ongelmia, joissa meille annetaan sanoja tuntemattomasta kielestä ja meidän on arvattava kieli. Nämä ovat kielen päättelyongelmia.
7. Kun otetaan huomioon joukko XML-dokumentteja, haluat muuttaa näiden asiakirjojen mallin. XML-asiakirjat voidaan idealisoida puiksi. Kaavio on tällöin puukielen erittely ja skeeman päättelyongelma on kielen päättelyongelma puukielille.
8. Monet sovellukset edellyttävät automaattista aritmeettista päättelyä. Oletetaan, että korjaamme loogisen teorian, kuten Presburgerin aritmeettisen, jossa meillä on luonnolliset luvut, yhteenlasku ja vähemmän kuin predikaatti. Kaava, jossa on n muuttujaa, edustaa joukkoa n-ulotteisia vektoreita. Vektori on numerosarja, ja se voidaan koodata sanana. Predikaatti on sitten joukko sanoja; kieli. Loogisista operaatioista, kuten yhdistelmä, disjunktio ja kieltäminen, tulee kielten leikkauspiste, liitto ja täydennys (eksistentiaalinen kvantifiointi on eräänlainen projektio).

Edellä vihjattu pelkistys käsittelee kieliä abstrakteina matemaattisina kohteina. Näiden ideoiden soveltamiseksi käytännössä tarvitsemme tietorakenteen edustamaan kieliä ja algoritmeja näiden tietorakenteiden manipuloimiseksi.

Syötä automaatit. Automaattien avulla voimme vähentää abstrakteja matemaattisia objekteja, kuten kieliä, koskevia kysymyksiä konkreettisiksi, algoritmisiksi kysymyksiksi leimattujen kaavioiden suhteen. Kielet ja automaatiteoria tarjoavat mielettömän määrän käytännön sovelluksia lukuun ottamatta erittäin merkittävän älyllisen palvelun. Voimme miettiä ongelmia, jotka vaihtelevat postinumeroiden muotoilemisesta päätöksentekomenettelyihin monadiista toisen asteen logiikkaa varten yhtenäisessä ja selkeässä käsitteellisessä tilassa. Kuinka mahtavaa onkaan!

En ole sanonut mitään logiikasta ja päätöksentekomenettelyistä. (Kyllä, heillä on käytännön sovelluksia.) Katso Kavehin vastauksesta auktoriteettinen yleiskatsaus.

Kommentit

• haha, ironia

Kuten muissa vastauksissa selitettiin, automaatiteoria on käsitteellisesti tärkeä yksinkertainen laskentamalli, jonka ymmärrämme hyvin, ja säännöllisillä lausekkeilla ja automaateilla on monia tosielämän sovelluksia.

Tässä on pieni esimerkki nykyaikaisesta tutkimuksesta, joka palaa automaatiteoriaan modernin käsitteen ymmärtämiseksi. Tässä artikkelissa tutkijat todistavat, että kaikilla tavallisilla kielillä on omaisuuden testaajia: ”Säännölliset kielet ovat testattavissa vakiomäärällisellä kyselyllä”

Se ei ole vain vanilja-automaatteja. Opit (laskennallisen) perusasiat (tilojen hyväksyminen, epsilon-siirtymät jne.) malli, joka auttaa päättelemään, mitä voi, ja mikä tärkeintä, mitä ei voida ilmaista joillakin kyselykielillä. Muutamia mielenkiintoisia tuloksia ovat:

• kyllä, kuuluisa tulos on, että Deterministiset äärelliset automaatit tunnistavat tavalliset kielet – joten nyt tiedät mitä tarvitset säännöllisen lausekekohdistuksen käyttöönottamiseksi.
• Puthdown Automata tunnistaa kontekstittomat kieliopit – nyt sinulla on idea siitä, miltä jäsennin näyttää (tai ainakin suuren luokan niistä).
• puuautomaatti tunnista lauseet yksitahoisen toisen asteen logiikan yli – nyt sinulla on käsitys siitä, mitä tarvitaan rajoitusten ohjelmointikielien toteuttamiseen tai … esimerkiksi joitain lauseita SQL: ssä .

(ja tietysti ohitan paljon muista luokista)

Periaatteessa se on hyvin yleinen malli. Oppitunnissasi korostetaan todennäköisesti yhteyttä automaattien, kielten ja logiikan välillä.

Jos etsin tämän liittämistä konkreettisiin ”maallisiin” työkaluihin, vietin rauhallisen aamun kirjastossa lukemalla pari osaa (AB?) kohdasta Perustiedot tietokannoista , kirjoittanut Abiteboul & al, ja yrittää yhdistää tämän takaisin luokan aineistoon. Tietenkin se on vain yksi (monista) tavoista etsiä automaatioluokan sovelluksia, ja luulen, ettei se ole ilmeisin – mutta se on juuri siksi mielenkiintoinen harjoitus.

Kuten useissa vastauksissa jo todettiin, UG-kurssien Automata Theory antaa yhdelle peruskäsitteellisen kehyksen edistyneempien (ja käytännön) aiheiden esittelyyn. huomaamatta jääneiden yhteyksien osoittamiseksi; esimerkiksi: Binaariset päätöksentekokaaviot (ne minimoidaan DFA; opetettuani DFA: n opetan usein BDD-pohjaista pulmaratkaisua); komentosarjat, mukaan lukien BioPerl ja BioPython (ja loistava asetus vahvistaa, kuinka monta ei-toivottua ottelua voidaan piilottaa reaalimaailman komentosarjojen uudelleenohjauksissa), virallinen virheenkorjaus (valtion ominaisuudet kuten hylätty FA, leikkaavat) ja jopa videonauhurin tai kodin tunkeilijan hälytysohjelmointi (päivittäin huonosti määritellyn automaatin stressitilanne, joka on opetettu epätäydellisten esimerkkien avulla; ehkä formalisoitu käyttämällä Harelin play-in / play-out-skenaarioon perustuvaa käyttöliittymien synteesiä.) Käytän myös asetusta Pythonin opettamiseen (melkein) puhtaasti toiminnallinen osajoukko, mukaan lukien kartat, lambdat ja joukkorajoitukset, joiden avulla voidaan koodata tavalliset FA-algoritmit, usein käytännöllisesti katsoen erotettavissa matematiikan defneistä.

Kommentit

• Tervetuloa, Ganesh!
• Mukava tapa opettaa automaatteja. Olisitko valmis jakamaan luentomuistiinpanosi?

Automaattiteoriaan on tehty huomattavaa tutkimusta teollisuuden mallintarkastuksessa. Tarkista Moshe Vardin äskettäiset luennot Fields-instituutissa , erityisesti 3. luento ”Logiikka, automaatit, pelit ja algoritmit”. edelleen tärkeä ja hyödyllinen.

Tiivistelmä:

Buechin, Elgotin, Rabinin ja Trakhtenbrot 1950- ja 1960-luvulla on yksi perustavanlaatuisimmista lähestymistavoista päätöksentekomenettelyihin. Viime aikoina tämä lähestymistapa on löytänyt teollisia sovelluksia laitteisto- ja ohjelmistojärjestelmien virallisessa todentamisessa. Polku logiikasta käytännön algoritmeihin kulkee paitsi automaattien lisäksi myös pelien kautta, joiden algoritmeja tarkastelivat Chandra, Kozen ja Stockmeyer 1970-luvun lopulla. Tässä yleiskatsauksessa kuvaamme polun logiikasta algoritmeihin automaattien ja pelien kautta.

Luentojen diat ja äänitiedostot ovat saatavilla täältä: 1 , 2 , 3 .

Heitän toisen vastauksen esiin aivan erilaisesta käytännön näkökulmasta: tekoälyssä käytetään usein äärellisiä tilakoneita (tai ainakin joitain niiden yksinkertaisia yleistyksiä / laajennuksia). puolella pelin ohjelmointia. Ne osoittautuvat tarjoamaan erinomaisen mallin kapseloimaan hahmokäyttäytymistä; esimerkiksi vihollisella voi olla valtioita, jotka edustavat ”partiointia”, ”etsintää”, ”lähestymistä”, ”hyökkäystä”, ”puolustusta”, ”vetäytymistä”, ”kuolemaa” jne., joiden välillä on tarkat siirtymät. Tähän ei liity mitään automaattien muodollisia piirteitä, kuten tavalliset kielet ja vastaavat, mutta automaatin käsite on hyvin ydin.

Olemme nähneet, että teoriaa ja käytäntöä vastakkain asettava kieli, joka asettaa toisen päällekkäin, on juuri lopputulos tietämättömyydestä – että se osoittaa miehen olevan tuntematon ensimmäisistä ajatuksen osista, ja se on loistava tapa osoittaa hänen mielensä olevan niin perverssi, ettei kykene opettamaan heitä. 2993218e52 ”>

Meidän tulisi ottaa huomioon sanojen ”käytännön” ja ”soveltaminen” semantiikka. Joillekin opiskelijoille käytännöllinen on mikä tahansa, mikä auttaa heitä suorittamaan kokeensa; muille mitä tahansa, mikä tulee esiin työssä. Kummassakin tapauksessa Automata Theory on todellakin hyvin käytännöllinen.

Kuten muut huomauttavat, käytät kielioppeja esimerkiksi opiskellessasi kääntäjiä. Mutta vielä enemmän: ymmärtämällä koko konseptin, jonka mukaan eri tilat ja väliset siirtymäsäännöt ovat niiden välillä, voi tehdä sinusta paremman ohjelmoijan, kun huomaat esimerkiksi, että koodisi on tarpeeton täällä ja siellä ja että kun parannat sitä, käyttävät koodissasi samoja käsitteellisiä ideoita DFA-minimoinnin takana.

Vastaavasti ”sovellus”. Mitä ymmärrät tällä sanalla? Vaikka olisitkin ”maanläheinen insinööri”, näet ja käytät todellisissa projekteissa samanlaisia ideoita kuin Automata Theory: ohjelmointikoodi, vuokaaviot ja jopa yksinkertainen mutta loistava pinon käsite. Minun kaltaisille teoriapojille pidän automaatioteorian sovelluksia muilla aloilla, kuten logiikka, algebra ja rajallinen malliteoria. En todellakaan tarvitse koskaan käyttää pumppaavaa lemmaa ostoksilla supermarketissa, mutta sellaiset lauseet ovat auttaneet minua ymmärtämään rakennetta tiettyjen kielten luokkiin, puhumattakaan logiikoista ja algebrallisista rakenteista, joiden kanssa ne ovat yhteensopivia. Ja sitä arvostan enemmän kuin mitä tahansa käytännöllisyyden mittausta.

Yhdessä logiikan kanssa automaatit voivat tarjota tapoja tarkista vanhemmat, kuten

$ \ qquad A \ models \ varphi $

automaattille $ A $ ja kaavalle $ \ varphi $. Jos $ A $ on järjestelmän malli ja $ \ varphi $ muodostaa halutut ominaisuudet, saat järjestelmän vahvistuksen, mikä on erittäin käytännöllinen huolenaihe yhä useammalle toteutettavissa olevalle sovellukselle.

Asioiden automaattipuoli huomioon ottaen johtaa hienoihin algoritmeihin. Esimerkiksi, jos $ \ varphi $ on LTL kaava ja $ A $ Büchi-automaatti (eli äärettömän käynnissä oleva äärellinen automaatti), voit kääntää $ \ varphi $ vastaavaan automaattiin $ A_ \ varphi $ ja tarkista, onko $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Äärellisiä automaatteja, joista kirjoitetaan usein rajallisina tilakoneina eri tilanteissa, tai niiden todennäköisyysvarianttien avulla piilotettuja Markov-malleja voidaan soveltaa kuvion tunnistamiseen ja kuvion rakenteeseen. Esimerkiksi. mikä on pienin stokastinen äärellinen automaatti, joka tuottaa merkkijonoja, enemmän tai vähemmän tietyn todennäköisyysjakauman mukaan, tai vastaavien tilastollisten ominaisuuksien merkkijono (tai aikasarja) otos jostakin jakaumasta.

Katso esimerkiksi CSSR , algoritmi piilotilojen sokeaan rekonstruointiin; se on tehokkaampaa ja joustavampaa kuin piilotetut Markov-mallit.

Kommentit

• Käytännön puolelle lisätään piilotettuja Markov-malleja puheentunnistuksessa. ohjelmat, kuten Kurzweil.

Toinen käytännöllisempi automaattiteorian sovellus on tekoälyn kehittäminen. Tekoäly kehitettiin äärellisen automaatin käsitteestä. Robottien hermoverkko rakennetaan automaatiteorian perusteella. Loppujen lopuksi robotit ovat myös automaatteja.

Jotkut ovat antaneet hyviä vastauksia sen suhteen, miten se suhtautuu teollisuuteen. Tärkeää pitäisi olla sen tieteellinen arvo, ja automaatiteoria on usein ovi ymmärtää korkeampi laskentateoria perustutkinnon suorittaneiden opiskelijoiden opinnoissa. Automaattiteoriassa on laaja joukko lauseita, jotka tulevat esiin kaikkialla tietojenkäsittelyteoriassa, ja varsinkin kun halutaan puhua sovelluksista, kuten kääntäjät. Sen tieteellinen arvo (ei ole vanhentunut, miten se voisi olla? Se on ydinteoria kentälle.) On käytännöllinen kaikille laskennasta kiinnostuneille tiedemiehille. Se on käytännöllistä, koska tieto on hyödyllistä niille, jotka ymmärtävät tai haluavat ymmärtää laskennan luonteen. Jos et löydä siitä käyttöä, kyseenalaistan tutkimuksen tai jopa aikomuksen tutkia CS: tä, koska se ei ohjelmoi (se on CS: n sovellus), se on muodollinen tiede.