Wie praktisch ist die Automatentheorie?

Es gibt immer eine Möglichkeit zur Anwendung in Themen der theoretischen Informatik. Lehrbücher und Grundstudiengänge erklären jedoch in der Regel nicht, warum die Automatentheorie ein wichtiges Thema ist und ob sie in der Praxis noch Anwendung findet. Daher haben Studenten im Grundstudium möglicherweise Probleme, die Bedeutung der Automatentheorie zu verstehen, und denken, dass sie keinen praktischen Nutzen mehr hat.

Ist die Automatentheorie in der Praxis noch nützlich?

Sollte es Teil des CS-Lehrplans für Studenten sein?

1. Hast du jemals ein Tool wie grep / awk / sed benutzt? Reguläre Ausdrücke bilden das Herzstück dieser Tools.

2. Sie werden überrascht sein, wie viel Codierung Sie durch die prinzipielle Verwendung regulärer Ausdrücke vermeiden können - in "praktischen Projekten" wie einem E-Mail-Server.

3. Wenn Sie ein CS-Hauptfach sind, schreiben Sie auf jeden Fall einen Compiler / Interpreter für eine (zumindest eine kleine) Sprache. Wenn Sie diese Aufgabe schon einmal ausprobiert haben und nicht weiterkommen, werden Sie es zu schätzen wissen, wie viel Ihnen eine kleine Theorie (auch als kontextfreie Grammatik bezeichnet) helfen kann. Diese Theorie hat eine einmal unmögliche Aufgabe zu etwas gemacht, das über ein Wochenende abgeschlossen werden kann. (Und es gewann der Erfinder einen Turing Award - Google BNF).

4. Wenn Sie ein CS-Major sind, müssen Sie sich irgendwann zurücklehnen und über die philosophischen Grundlagen des Computing nachdenken und nicht nur darüber, wie cool die nächste Version der Android-API ist. In diesem Zusammenhang ist es die Aufgabe der Universität, Sie nicht auf die nächsten 5 Jahre Ihres Lebens vorzubereiten, sondern auf die nächsten 50 Jahre vorzubereiten. Das einzige, was sie in dieser Hinsicht tun können, ist, Ihnen zu helfen, nachzudenken - nachzudenken der Automatentheorie als einer dieser Kurse.

Eine der praktischeren Erscheinungsformen von CS ist die Compilerkonstruktion. 1965 begann Knuth mit der Untersuchung von LR-Parsern. Schnell (in weniger als einem Jahrzehnt) hatten wir LALR-Parser, eine Untergruppe deterministischer Pushdown-Automaten, mit denen wir Shift- / Reduction-Parser implementieren können.

Im Zentrum der Machbarkeit und Effizienz des LALR-Parsings steht der Beweis (von Knuth), dass "Präfixe" der Sprache regelmäßig sind (Ihr endlicher Automat). Dies ist die Genese von automatisierten Parser-Generatoren wie Yacc / Bison usw.

Man kann mit Sicherheit sagen, dass Programmiersprachen, wie wir sie kennen, einen großen Teil ihrer Kompilierungseffizienz diesen Entwicklungen verdanken.

Hier ist ein weiteres Beispiel: Das Herzstück des TCP / IP-Protokolls ist eine Zustandsmaschine. Wie viel praktischer kann es werden?

Jeder ernsthafte CS-Student, insbesondere der praktische, sollte auf die Automatentheorie achten. Es ist die Grundlage für einen Großteil des Reichtums der Informatik.

Kannst du das Geräusch hören ? Es ist der Klang von tausend brillanten Theoremen, Anwendungen und Werkzeugen, die im Himmel der Automatentheorie lachen.

Sprachen und Automaten sind elegante und robuste Konzepte, die Sie in allen Bereichen der Informatik finden. Sprachen sind keine trockenen, formalistischen Überlieferungen aus der Urgeschichte. Die sprachtheoretische Perspektive destilliert scheinbar komplizierte Fragen nach raffinierten, undurchsichtigen Objekten in einfache Aussagen über Wörter und Bäume. Formale Sprachen spielen in der Informatik eine ähnliche Rolle wie die grundlegende und wegweisende Sichtweise, die Algebra und Topologie der klassischen Mathematik verleihen. Hier sind einige praktische, ziemlich komplizierte, praktische Probleme, die über die Sprachtheorie angegangen werden.

1. Sie möchten doppelte Vorkommen einer Phrase in einem Dokument erkennen und das zweite Vorkommen löschen. Im Wesentlichen möchten Sie eine Sequenz in einer Sprache ersetzen.
2. Enthält ein Programm eine Behauptungsverletzung? Respektiert ein Gerätetreiber bestimmte Protokolle bei der Interaktion mit dem Kernel? Das Verhalten eines Programms ist eine Reihe von Ausführungen; mit anderen Worten, eine Sprache. Die Korrektheitseigenschaft ist eine andere Sprache. Das Programmkorrektheitsproblem läuft auf eine Überprüfung der Spracheinbeziehung hinaus.
3. Kann Ihre Software in einer Endlosschleife stecken bleiben? Enthält ein verteilter Algorithmus eine Livelock? Wir brauchen Sprachen über unendliche Wörter, aber die Ansicht der Einbeziehung von Sprachen gilt weiterhin.
4. Sie möchten ein Desinfektionsprogramm erstellen, um schädliches JavaScript zu erkennen, das in eine Webanwendung eingegeben wurde. Die Menge der schädlichen Zeichenfolgen ist eine Sprache. Die Zeichenfolgen, die in einer anderen Sprache in die Formulare eingegeben wurden. Sie möchten feststellen, ob die Schnittmenge dieser Sprachen nicht leer ist.
5. Laufzeitüberwachung von reaktiven und geschäftskritischen Systemen. Sie möchten einen Software-Monitor entwerfen, der den Betrieb Ihres chemischen Prozesses überwacht oder Aktualisierungen einer Finanzdatenbank nachverfolgt. Dies sind Kernprobleme bei der Einbeziehung von Sprachen und Schnittmengen.
6. Mustererkennung mit ihren zahlreichen Anwendungen. Sie möchten Muster in genomischen Daten, in Text und in einer Reihe von Fehlerberichten erkennen. Dies sind Probleme, bei denen wir Wörter aus einer unbekannten Sprache erhalten und die Sprache erraten müssen. Dies sind Probleme mit Sprachschlüssen.
7. Bei einer Reihe von XML-Dokumenten möchten Sie ein Schema zurückentwickeln, das für diese Dokumente gilt. XML-Dokumente können in Bäumen idealisiert werden. Ein Schema ist dann eine Spezifikation einer Baumsprache, und das Problem der Schema-Inferenz ist ein Problem der Sprachinferenz über Baumsprachen.
8. Viele Anwendungen erfordern automatisierte arithmetische Überlegungen. Nehmen wir an, wir legen eine logische Theorie wie die Presburger-Arithmetik fest, in der wir die natürlichen Zahlen, die Addition und das Prädikat kleiner als haben. Eine Formel mit n Variablen repräsentiert eine Menge von n-dimensionalen Vektoren. Ein Vektor ist eine Folge von Ziffern und kann als Wort codiert werden. Ein Prädikat ist dann eine Menge von Wörtern; eine Sprache. Logische Operationen wie Konjunktion, Disjunktion und Negation werden zu Schnittpunkten, Vereinigungen und Komplementen von Sprachen (existentielle Quantifizierung ist eine Art Projektion).

Die oben angedeutete Reduktion behandelt Sprachen als abstrakte mathematische Objekte. Um diese Ideen in die Praxis umzusetzen, benötigen wir eine Datenstruktur zur Darstellung von Sprachen und Algorithmen zur Manipulation dieser Datenstrukturen.

Automaten eingeben. Mit Hilfe von Automaten können wir Fragen zu abstrakten mathematischen Objekten wie Sprachen auf konkrete algorithmische Fragen zu beschrifteten Graphen reduzieren. Sprachen- und Automatentheorie bieten neben einer verrückten Anzahl von praktischen Anwendungen einen sehr bedeutenden intellektuellen Dienst. Wir können über Probleme nachdenken, die von der Formatierung von Postleitzahlen bis zu Entscheidungsprozeduren für monadische Logik zweiter Ordnung in einem einheitlichen und übersichtlichen konzeptuellen Raum reichen. Wie großartig ist das!

Ich habe nichts über Logik und Entscheidungsverfahren gesagt. (Ja, sie haben praktische Anwendungen.) Eine aussagekräftige Übersicht finden Sie in Kavehs Antwort.

Wie in den anderen Antworten erläutert, ist die Automatentheorie konzeptionell als einfaches Rechenmodell wichtig, das wir gut verstehen, und reguläre Ausdrücke und Automaten haben viele reale Anwendungen.

Hier ist ein kleines Beispiel für die moderne Forschung, das auf die Automatentheorie zurückgeht, um ein modernes Konzept zu verstehen. In dieser Arbeit beweisen Forscher, dass reguläre Sprachen alle Eigenschaftstester haben: "Reguläre Sprachen können mit einer konstanten Anzahl von Abfragen getestet werden."

Es sind nicht nur Vanille-Automaten. Sie lernen die Grundlagen (Akzeptieren von Zuständen, Epsilon-Übergängen, ...) eines (rechnerischen) Modells kennen, mit dessen Hilfe Sie überlegen können, was in manchen Abfragesprachen ausgedrückt werden kann und was nicht. Einige interessante Ergebnisse sind:

• Ja, das berühmte Ergebnis ist, dass deterministische endliche Automaten reguläre Sprachen erkennen. Jetzt wissen Sie also, was Sie zum Implementieren des Abgleichs regulärer Ausdrücke benötigen.
• Pushdown-Automaten erkennen kontextfreie Grammatiken - jetzt haben Sie eine Vorstellung davon, wie ein Parser aussieht (oder zumindest eine große Klasse davon).
• Baumautomaten erkennen Anweisungen über die monadische Logik zweiter Ordnung - jetzt haben Sie eine Vorstellung davon, wie Sie einige Programmiersprachen für Einschränkungen implementieren müssen, oder ... einige Anweisungen in SQL , zum Beispiel.

(und natürlich überspringe ich viele andere Klassen)

Grundsätzlich ist es ein sehr allgemeines Modell. Ihre Klassen werden wahrscheinlich die Verbindung zwischen Automaten, Sprachen und Logik betonen.

Wenn ich dies mit konkreten "weltlichen" Werkzeugen in Verbindung bringen wollte, verbrachte ich einen entspannten Vormittag in der Bibliothek, um ein paar Teile (AB?) Aus Foundations of Databases von Abiteboul & al zu lesen und zu versuchen, diese mit dem Unterrichtsmaterial in Verbindung zu bringen . Natürlich ist es nur eine der (vielen) Möglichkeiten, nach Anwendungen einer Automatenklasse zu suchen, und ich denke nicht die offensichtlichste - aber genau deshalb ist es eine interessante Übung.

Wie bereits in verschiedenen Antworten erwähnt, bietet Automata Theory in UG-Kursen den grundlegenden konzeptionellen Rahmen für die Einführung fortgeschrittenerer (und praktischer) Themen sowie für die Hervorhebung übersehener Zusammenhänge. Zum Beispiel: Binäre Entscheidungsdiagramme (sie sind minimierte DFA; nach dem Unterrichten von DFA unterrichte ich oft BDD-basierte Rätsellösungen); Skripterstellung, einschließlich in BioPerl und BioPython (und eine großartige Einstellung, um zu verstärken, wie viele unbeabsichtigte Übereinstimmungen in regulären Skript-Regexps versteckt sein können), formelles Debugging (Zustandseigenschaften wie negierter FA, Überschneidung) und sogar VCR- oder Home-Intruder-Alarm-Programmierung (Alltagsstresssituation eines schlecht spezifizierten Automaten anhand unvollständiger Beispiele; möglicherweise formalisiert mit Harels szenariobasierter Synthese von Benutzerschnittstellen zum Ein- und Ausspielen). Ich benutze die Einstellung auch, um Python zu unterrichten. '

Ich werde eine andere Antwort aus einem ganz anderen praktischen Blickwinkel heraus werfen: Finite-State-Maschinen (oder zumindest einige einfache Verallgemeinerungen / Erweiterungen davon) werden häufig auf der KI-Seite der Spielprogrammierung verwendet. Sie bieten ein hervorragendes Modell für die Verkapselung des Charakterverhaltens. Zum Beispiel könnte ein Feind Staaten haben, die "Patrouille", "Suche", "Annäherung", "Angriff", "Verteidigung", "Rückzug", "Sterben" usw. mit genau definierten Übergängen zwischen ihnen darstellen. Dies beinhaltet keine der formalen Aspekte von Automaten wie reguläre Sprachen und dergleichen, aber das Konzept des Automaten ist ein sehr zentrales.

Wir haben gesehen, dass die Sprache, die Theorie und Praxis gegenüberstellt und die eine über die andere stellt, die Vollendung der Unwissenheit ist - sie beweist, dass ein Mann mit den allerersten Elementen des Denkens nicht vertraut ist und einen großen Beitrag dazu leistet, seine Unwissenheit zu beweisen dagegen, so pervers zu sein, dass man sie nicht lehren kann.

- James Mill (Pseudonym "PQ"), "Theory and Practice", London und Westminster Review , April 1836

Es wurden beträchtliche Forschungen im Zusammenhang mit der Automatentheorie bei der in der Industrie verwendeten Modellprüfung durchgeführt. In den jüngsten Vorlesungen von Moshe Vardi am Fields Institute , insbesondere in der dritten Vorlesung "Logik, Automaten, Spiele und Algorithmen", erfahren Sie, warum die Automatentheorie immer noch wichtig und nützlich ist.

Abstrakt:

Der automaten-theoretische Ansatz für Entscheidungsverfahren, den Buechi, Elgot, Rabin und Trakhtenbrot in den 1950er und 1960er Jahren eingeführt haben, ist einer der grundlegendsten Ansätze für Entscheidungsverfahren. In letzter Zeit hat dieser Ansatz industrielle Anwendungen bei der formalen Verifizierung von Hardware- und Softwaresystemen gefunden. Der Weg von der Logik zu praktischen Algorithmen führt nicht nur über Automaten, sondern auch über Spiele, deren algorithmische Aspekte Ende der 1970er Jahre von Chandra, Kozen und Stockmeyer untersucht wurden. In diesem Übersichtsvortrag beschreiben wir den Weg von der Logik zu den Algorithmen über Automaten und Spiele.

Die Folien und Audiodateien der Vorträge finden Sie hier: 1 , 2 , 3 .

Wir sollten die Semantik der Wörter "praktisch" und "Anwendung" berücksichtigen. Praktisch ist für einige Studenten alles, was ihnen hilft, ihre Prüfungen zu bestehen. für andere alles, was in einem Job auftaucht. In beiden Fällen ist die Automatentheorie in der Tat sehr praktisch.

Wie bereits erwähnt, verwenden Sie Grammatiken beispielsweise beim Studium von Compilern. Aber noch mehr als das: Wenn Sie das gesamte Konzept der unterschiedlichen Zustände und Regeln für Übergänge zwischen ihnen verstehen, können Sie ein besserer Programmierer werden, wenn Sie beispielsweise feststellen, dass Ihr Code hier und da redundant ist und wenn Sie ihn verbessern ist die Anwendung in Ihrem Code die gleichen konzeptionellen Ideen hinter DFA Minimierung.

Ähnliches gilt für "Bewerbung". Was verstehst du unter diesem Wort? Selbst wenn Sie ein "bodenständiger Ingenieur" sind, werden Sie Ideen, die denen der Automatentheorie ähneln, in realen Projekten sehen und anwenden: Programmcode, Flussdiagramme und sogar das einfache, aber brillante Konzept eines Stapels. Für theoretische Nerds wie mich betrachte ich Anwendungen der Automatentheorie in anderen Bereichen wie Logik, Algebra und Finite-Modell-Theorie. Sicherlich werde ich das Pumplemma beim Einkaufen in einem Supermarkt nie brauchen, aber solche Sätze haben mir geholfen, die Struktur bestimmter Klassen von Sprachen zu verstehen , ganz zu schweigen von den logischen und algebraischen Strukturen, mit denen sie korrespondieren. Und das schätze ich mehr als jedes Maß an Praktikabilität.

Zusammen mit Logiken können Automaten Möglichkeiten bieten, Zustände wie zu überprüfen

$\qquad A \models \varphi$

$A$$\varphi$$A$$\varphi$

$\varphi$$A$$\varphi$$A_\varphi$$\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Endliche Automaten, oft als endliche Automaten in verschiedenen Kontexten oder mit ihren probabilistischen Varianten beschrieben, können zur Mustererkennung und zur Quantifizierung der Struktur eines Musters verwendet werden. ZB was ist die kleinste stochastische endliche Automate, die Zeichenfolgen mehr oder weniger nach einer bestimmten Wahrscheinlichkeitsverteilung erzeugt, oder welche statistischen Eigenschaften einer Stichprobe von Zeichenfolgen (oder Zeitreihen) aus einer bestimmten Verteilung übereinstimmen.

Siehe zum Beispiel CSSR , einen Algorithmus zur blinden Rekonstruktion verborgener Zustände; Es ist effizienter und flexibler als Hidden Markov Models.

Eine weitere praktischere Anwendung der Automatentheorie ist die Entwicklung der künstlichen Intelligenz. Künstliche Intelligenz wurde aus dem Konzept des endlichen Automaten entwickelt. Das neuronale Netzwerk der Roboter ist auf Basis der Automatentheorie aufgebaut. Schließlich sind Roboter auch Automaten.

Einige haben großartige Antworten gegeben, wenn es darum geht, wie es sich auf die Industrie bezieht. Was wichtig sein sollte, ist sein wissenschaftlicher Wert, und die Automatentheorie ist oft die Tür zum ersten Verständnis einer höheren Stufe der Berechnungstheorie im Studium eines Studenten. In der Automatentheorie gibt es eine ganze Reihe von Theoremen, die in der theoretischen Informatik überall auftauchen, insbesondere wenn man über Anwendungen wie Compiler sprechen möchte. Sein wissenschaftlicher Wert (nicht veraltet, wie könnte es sein? Es ist die Kerntheorie des Fachs.) Ist praktisch für jeden Wissenschaftler, der sich für Berechnungen interessiert. Es ist praktisch, da es Wissen ist, das für diejenigen nützlich ist, die die Natur der Berechnung verstehen oder verstehen wollen. Wenn Sie keine Verwendung darin finden können, stelle ich die Forschung oder sogar die Absicht in Frage, CS zu studieren, da es sich nicht um Programmierung handelt.