Hoe praktisch is de automaattheorie?

1. Ooit een tool als grep / awk / sed gebruikt? Reguliere expressies vormen het hart van deze tools.

2. Het zal je “verbazen hoeveel codering je kunt vermijden door principieel gebruik te maken van reguliere expressies – in” praktische projecten “, zoals een e-mail server.

3. Als je een CS major bent, zul je zeker een compiler / interpreter schrijven voor een (tenminste een kleine) taal. Als je ooit hebt geprobeerd deze taak eerder en liep vast, je zult waarderen hoeveel een beetje theorie (ook wel contextvrije grammatica genoemd) je kan helpen. Deze theorie heeft van een ooit onmogelijke taak iets gemaakt dat in een weekend kan worden voltooid. (en het won de uitvinder een Turing-onderscheiding – google BNF).

4. Als je een CS-majoor bent, moet je op een gegeven moment achterover leunen en nadenken over de filosofische grondslagen van computergebruik, en niet ongeveer hoe cool de volgende versie van de Android API is. In verband daarmee is het de taak van de universiteit om je niet voor te bereiden op de komende 5 jaar van je leven, maar om je voor te bereiden op de volgende 50 jaar. Het enige wat ze in dit verband kunnen doen, is je helpen na te denken – na te denken van automaattheorie als een van die cursussen.

Een van de meer praktische manifestaties van CS is Compiler Construction. In 1965 begon Knuth met de studie van LR-parsers. We hadden snel (in minder dan een decennium) LALR-parsers die een subset zijn van deterministische pushdown-automaten waarmee we shift / reductie-parsers kunnen implementeren.

De kern van de haalbaarheid en efficiëntie van LALR-parsing is een bewijs (door Knuth) dat “voorvoegsels” van de taal regelmatig blijken te zijn (uw eindige automaat). Dit is het ontstaan van geautomatiseerde parser-generatoren zoals yacc / bison enz.

Het is veilig om te zeggen dat programmeertalen zoals we die kennen veel van hun compileerefficiëntie te danken hebben aan deze ontwikkelingen.

Hier is nog een voorbeeld: het hart van het TCP / IP-protocol is een eindige toestandsmachine. Hoeveel praktischer kan het worden?

Elke serieuze CS-student, vooral de praktische, zou aandacht moeten besteden aan automatenleer. Het is de basis voor veel van de rijkdom van Computer Science.

Reacties

• Het parseren van bronbestanden is niet echt het interessante (en belangrijke) deel van een compiler, dus ik doe ‘ denk niet dat het veilig is om te zeggen dat ” programmeertalen zoals we die kennen veel van hun compilatie-efficiëntie te danken hebben aan deze ontwikkelingen “. Bovendien is het mogelijk om talen te ontleden met behulp van verschillende tools, bijvoorbeeld PEGs of parseercombinatoren (bijv. Parsec).

Hoor je dat geluid ? Het is het geluid van duizend briljante stellingen, toepassingen en gereedschappen die lachen in de automaten-theoretische hemel.

Talen en automaten zijn elegante en robuuste concepten die u in elk gebied van de informatica aantreft. Talen zijn geen droge, formalistische hand-me-downs uit de prehistorie van computers.Vanuit het perspectief van de taaltheorie worden ogenschijnlijk gecompliceerde vragen over geavanceerde, ondoorzichtige objecten omgezet in eenvoudige uitspraken over woorden en bomen. Formele talen spelen een rol in de informatica, verwant aan het fundamentele en spelveranderende standpunt dat door algebra en topologie in de klassieke wiskunde wordt ingebracht. Hier zijn enkele praktische, vrij ingewikkelde, praktische problemen die via taaltheorie worden benaderd.

1. U wilt dubbele exemplaren van een zin in een document opsporen en de tweede instantie verwijderen. In wezen wil je een reeks in een taal vervangen.
2. Bevat een programma een schending van een bewering? Respecteert een apparaatstuurprogramma bepaalde protocollen bij interactie met de kernel? Het gedrag van een programma is een reeks uitvoeringen; met andere woorden, een taal. De correctheidseigenschap is een andere taal. Het correctheidsprobleem van het programma komt neer op een taalinclusiecontrole.
3. Kan uw software vastlopen in een oneindige lus? Bevat een gedistribueerd algoritme een livelock? We hebben talen nodig in plaats van oneindig veel woorden, maar de weergave van het opnemen van talen is nog steeds van toepassing.
4. U wilt een ontsmettingsmiddel bouwen om kwaadaardig Javascript te detecteren dat in een webtoepassing is ingevoerd. De set van kwaadaardige strings is een taal. De reeks strings die in de formulieren in een andere taal zijn ingevoerd. U wilt bepalen of de kruising van deze talen niet leeg is.
5. Run-time monitoring van reactieve en bedrijfskritische systemen. U wilt een softwaremonitor ontwerpen die toezicht houdt op de werking van uw chemische proces of updates bijhouden in een financiële database. Dit zijn in wezen taalinsluitings- en kruispuntproblemen.
6. Patroonherkenning met zijn talrijke toepassingen. U wilt patronen detecteren in genomische gegevens, in tekst, in een reeks bugrapporten. Dit zijn problemen waarbij we woorden uit een onbekende taal krijgen en de taal moeten raden. Dit zijn problemen met het afleiden van taal.
7. Gegeven een set XML-documenten, wilt u een schema reverse-engineeren dat van toepassing is op deze documenten. XML-documenten kunnen worden geïdealiseerd in bomen. Een schema is dan een specificatie van een boomtaal en het schema-inferentieprobleem is een taalinferentieprobleem over boomtalen.
8. Veel toepassingen vereisen geautomatiseerde rekenkundige redenering. Stel dat we een logische theorie vastleggen, zoals Presburger-rekenkunde, waarin we de natuurlijke getallen, optellen en het predikaat kleiner dan hebben. Een formule met n variabelen vertegenwoordigt een reeks n-dimensionale vectoren. Een vector is een reeks cijfers en kan als een woord worden gecodeerd. Een predikaat is dan een reeks woorden; een taal. Logische bewerkingen zoals conjunctie, disjunctie en negatie worden intersectie, vereniging en complement van talen (existentiële kwantificering is een soort projectie).

De reductie waarnaar hierboven wordt verwezen, behandelt talen als abstracte wiskundige objecten. Om deze ideeën in de praktijk toe te passen, hebben we een datastructuur nodig om talen weer te geven en algoritmen om deze datastructuren te manipuleren.

Automaten invoeren. Met automaten kunnen we vragen over abstracte wiskundige objecten zoals talen terugbrengen tot concrete, algoritmische vragen over gelabelde grafieken. Talen en automatenleer leveren, naast een waanzinnig aantal praktische toepassingen, een zeer belangrijke intellectuele dienst op. We kunnen nadenken over problemen die variëren van het opmaken van postcodes tot besluitvormingsprocedures voor monadische tweede orde logica in een uniforme en overzichtelijke conceptuele ruimte. Hoe verbazingwekkend is dat!

Ik heb niets gezegd over logica en besluitvormingsprocedures. (Ja, ze hebben praktische toepassingen.) Zie het antwoord van Kaveh voor een gezaghebbend overzicht.

Opmerkingen

• haha, de ironie

Zoals uitgelegd in de andere antwoorden, is automaattheorie conceptueel belangrijk als een eenvoudig rekenmodel dat we goed begrijpen, en reguliere expressies en automaten hebben veel real-life toepassingen.

Hier is een klein voorbeeld voor modern onderzoek dat teruggaat naar de automaattheorie om een modern concept te begrijpen. In dit artikel bewijzen onderzoekers dat reguliere talen allemaal eigenschapstesters hebben: “Normale talen kunnen worden getest met een constant aantal zoekopdrachten”

Het zijn niet alleen vanille-automaten. Je leert over de basis (toestanden accepteren, epsilon-overgangen, …) van een (computationele) model dat helpt bij het redeneren over wat kan, en nog belangrijker, wat niet kan worden uitgedrukt met sommige zoektalen. Een paar interessante resultaten zijn:

• ja, het beroemde resultaat is dat Deterministische eindige automaten reguliere talen herkennen – dus nu weet je het wat je nodig hebt om het matchen van reguliere expressies te implementeren.
• Pushdown-automaten herkennen Contextvrije grammaticas – nu heb je een idee van hoe een parser eruitziet (of in ieder geval een grote klasse daarvan).
• boomautomaten herken verklaringen over monadische tweede-orde logica – nu heb je een idee van wat er nodig is om een aantal beperkende programmeertalen te implementeren , of … enkele instructies in SQL , bijvoorbeeld.

(en natuurlijk sla ik veel over van andere klassen)

In wezen is het een heel algemeen model. Je lessen zullen waarschijnlijk de link tussen automaten, talen en logica benadrukken.

Als ik dit in verband zou willen brengen met concrete “wereldse” gereedschappen, “zou ik een ontspannen ochtend in de bibliotheek hebben doorgebracht met het lezen van een paar delen (AB?) uit Fundamenten van databases door Abiteboul & al, en proberen dit weer te verbinden met klassemateriaal. Natuurlijk is het gewoon een van de (vele) manieren om naar toepassingen van een automaatklasse te zoeken, en ik denk niet de meest voor de hand liggende – maar dat is precies waarom het een interessante oefening is.

Zoals al aangegeven in verschillende antwoorden, geeft Automata Theory in RUG-cursussen een conceptueel basiskader voor het introduceren van meer geavanceerde (en praktische) onderwerpen, en ook voor het wijzen op over het hoofd geziene verbindingen; bijvoorbeeld: binaire beslissingsdiagrammen (ze zijn geminimaliseerd DFA; nadat ik DFA heb geleerd, geef ik vaak BDD-gebaseerde puzzels oplossen); scripting inclusief in BioPerl en BioPython (en een geweldige setting om te versterken hoeveel onbedoelde overeenkomsten verborgen kunnen zijn in real-world script-regexps), formele debugging (status eigenschappen als ontkend FA, kruisen), en zelfs VCR of huisinbraakalarmprogrammering (dagelijkse stresssituatie van een slecht gespecificeerde automaat aangeleerd door onvolledige voorbeelden; misschien geformaliseerd met behulp van Harels play-in / play-out scenario-gebaseerde synthese van gebruikersinterfaces). Ik gebruik de instelling ook om Pythons (bijna) puur te leren functionele subset, inclusief kaarten, lambdas en setbegrip, waarmee men standaard FA-algoritmen kan coderen, vaak op een manier die vrijwel niet te onderscheiden is van wiskundige definities.

Reacties

• Welkom, Ganesh!
• Een leuke manier om automaten te leren. Zou u bereid zijn uw aantekeningen te delen?

Er is veel onderzoek gedaan met betrekking tot automatenleer bij modelcontrole die in de industrie wordt gebruikt. Bekijk Moshe Vardis recente lezingen aan Fields Institute , in het bijzonder de derde lezing “Logic, Automata, Games, and Algorithms” om te zien waarom de automaattheorie is nog steeds belangrijk en nuttig.

Samenvatting:

De automaat-theoretische benadering van besluitvormingsprocedures, geïntroduceerd door Buechi, Elgot, Rabin en Trakhtenbrot in de jaren 50 en 60 is een van de meest fundamentele benaderingen van besluitvormingsprocedures. Onlangs heeft deze benadering industriële toepassingen gevonden bij de formele verificatie van hardware- en softwaresystemen. De weg van logica naar praktische algoritmen gaat niet alleen via automaten, maar ook via door middel van games, waarvan de algoritmische aspecten werden bestudeerd door Chandra, Kozen en Stockmeyer aan het einde van de jaren 70. In deze overzichtspraat beschrijven we het pad van logica naar algoritmen via automaten en games.

De slides en audiobestanden van lezingen zijn hier beschikbaar: 1 , 2 , 3 .

Ik “gooi een ander antwoord weg vanuit een geheel andere praktische invalshoek: eindige-toestandsmachines (of op zijn minst enkele eenvoudige generalisaties / uitbreidingen ervan) worden vaak gebruikt op de AI kant van het programmeren van games. Ze blijken een uitstekend model te zijn om karaktergedrag in te kapselen; een vijand kan bijvoorbeeld staten hebben die staan voor “patrouille”, “zoeken”, “naderen”, “aanvallen”, “verdedigen”, “terugtrekken”, “sterven”, enz. met goed gedefinieerde overgangen ertussen. Dit heeft geen betrekking op de formele aspecten van automaten zoals reguliere talen en dergelijke, maar het concept van de automaat is een zeer kernconcept.

We hebben gezien dat de taal die theorie en praktijk contrasteert door de ene boven de andere te plaatsen, de voltooiing is van onwetendheid – dat het bewijst dat een man niet bekend is met de allereerste elementen van het denken, en een geweldige manier is om te bewijzen dat zijn geest zo pervers is dat hij niet in staat is om ze te leren.

– James Mill (pseudoniem schrijft als” PQ”),“ Theory and Practice ”, London and Westminster Review , april 1836

We moeten rekening houden met de semantiek van de woorden “praktisch” en “toepassing”. Voor sommige studenten is praktisch alles dat hen zal helpen hun examens te halen; voor anderen, alles wat in een baan opkomt. In beide gevallen is Automata Theory inderdaad erg praktisch.

Zoals anderen aangeven, zul je bijvoorbeeld grammaticas gebruiken bij het bestuderen van compilers. Maar zelfs meer dan dat: als u het hele concept van verschillende toestanden en regels voor overgangen ertussen begrijpt, kunt u een betere programmeur worden als u zich bijvoorbeeld realiseert dat uw code hier en daar overbodig is, en dat wanneer u deze verbetert, u passen in uw code dezelfde conceptuele ideeën toe achter DFA-minimalisatie.

Evenzo voor “applicatie”. Wat versta je onder dat woord? Zelfs als u een “nuchtere ingenieur” bent, zult u ideeën zien en gebruiken die vergelijkbaar zijn met die van Automata Theory in echte projecten: programmeercode, stroomdiagrammen en zelfs het eenvoudige maar briljante concept van een stapel. Voor theorienerds zoals ik beschouw ik toepassingen van Automata Theory op andere gebieden, zoals logica, algebra en eindige modeltheorie. Ik zal het pompende lemma waarschijnlijk nooit hoeven gebruiken tijdens het winkelen in een supermarkt, maar dergelijke stellingen hebben me geholpen de -structuur van bepaalde taalklassen, om nog maar te zwijgen van de logica en algebraïsche structuren waarmee ze in overeenstemming zijn. En dat is iets waar ik meer waarde aan hecht dan enige mate van bruikbaarheid.

Samen met logica gegooid, kunnen automaten manieren bieden om controleer statemens zoals

$ \ qquad A \ models \ varphi $

voor een automaat $ A $ en een formule $ \ varphi $. Als $ A $ een model van een systeem is en $ \ varphi $ een formalisering van gewenste eigenschappen, krijg je systeemverificatie, een zeer praktische zorg met een groeiend aantal haalbare toepassingen.

Gezien de automatische kant van de dingen. leidt tot mooie algoritmen. Als $ \ varphi $ bijvoorbeeld een LTL -formule is en $ A $ a Büchi-automaat (dwz een oneindig lopende eindige automaat), kunt u $ \ varphi $ vertalen naar een gelijkwaardige automaat $ A_ \ varphi $ en controleer of $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Eindige automaten, vaak beschreven als eindige-toestandsmachines in verschillende contexten, of met hun probabilistische varianten Verborgen Markov-modellen kunnen worden toegepast op patroonherkenning en kwantificerende structuur van een patroon. Bijv. wat is de kleinste stochastische eindige automaat die strings zal genereren volgens, min of meer, een gegeven kansverdeling, of overeenkomende statistische eigenschappen van een steekproef van strings (of tijdreeksen) uit een bepaalde verdeling.

Zie bijvoorbeeld CSSR , een algoritme voor het blindelings reconstrueren van verborgen toestanden; het is efficiënter en flexibeler dan Hidden Markov-modellen.

Opmerkingen

• Om iets aan de praktische kant toe te voegen, worden Hidden Markov-modellen gebruikt bij spraakherkenning programmas zoals Kurzweil.

Een andere, meer praktische toepassing van automaattheorie is de ontwikkeling van kunstmatige intelligentie. Kunstmatige intelligentie is ontwikkeld vanuit het concept van eindige automaten. Het neurale netwerk van robots is geconstrueerd op basis van automatenleer. Robots zijn immers ook automaten.

Sommigen hebben geweldige antwoorden gegeven als het gaat om hoe het zich verhoudt tot de industrie. Wat belangrijk zou moeten zijn, is de wetenschappelijke waarde ervan, en de Automata-theorie is vaak de deuropening om eerst een hoger niveau van computertheorie te begrijpen in de studies van een niet-gegradueerde student. Automata-theorie heeft een groot aantal stellingen die overal in Theoretische Computerwetenschappen opduiken, en vooral wanneer men het wil hebben over toepassingen zoals Compilers. De wetenschappelijke waarde ervan (het is niet achterhaald, hoe zou het kunnen? Het is de kerntheorie voor het vakgebied.) Is praktisch voor elke wetenschapper die geïnteresseerd is in berekeningen. Het is praktisch omdat het kennis is die nuttig is voor degenen die het begrijpen of willen om de aard van de berekening te begrijpen. Als je er geen gebruik in kunt vinden, twijfel ik aan iemands onderzoek of zelfs de intentie om CS te bestuderen, omdat het geen programmeren is (dat is een toepassing van CS), het is een formele wetenschap.