Wie praktisch ist die Automatentheorie?

1. Haben Sie jemals ein Tool wie grep / awk / sed verwendet? 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 einer E-Mail Server.

3. Wenn Sie ein CS-Major sind, werden Sie definitiv einen Compiler / Interpreter für eine (zumindest kleine) Sprache schreiben. Wenn Sie es jemals versucht haben Diese Aufgabe vor und stecken geblieben, Sie werden es zu schätzen wissen, wie viel eine kleine Theorie (auch bekannt als kontextfreie Grammatik) Ihnen helfen kann. Diese Theorie hat eine einmal unmögliche Aufgabe zu etwas gemacht, das über ein Wochenende erledigt werden kann. (Und sie hat den Erfinder gewonnen eine Turing-Auszeichnung – Google BNF).

4. Wenn Sie ein CS-Major sind, müssen Sie sich irgendwann zurücklehnen und über die philosophischen Grundlagen des Rechnens nachdenken, und nicht 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 Sie auf die nächsten 50 Jahre vorzubereiten. Das einzige, was sie in dieser Hinsicht tun können, ist, Ihnen beim Denken – Denken zu helfen der Automatentheorie als einer dieser Kurse.

Eine der praktischeren Manifestationen von CS ist Compiler Construction. 1965 begann Knuth mit der Untersuchung von LR-Parsern. Schnell (in weniger als einem Jahrzehnt) hatten wir LALR-Parser, die eine Teilmenge deterministischer Pushdown-Automaten sind, mit denen wir Verschiebungs- / Reduzierungsparser implementieren können.

Im Zentrum der Machbarkeit und Effizienz der LALR-Analyse steht ein Beweis (von Knuth), dass sich „Präfixe“ der Sprache als regelmäßig herausstellen (Ihr endlicher Automat). Dies ist die Genese automatisierter 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 Finite-State-Maschine. Wie viel praktischer kann es werden?

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

Kommentare

• Das Parsen von Quelldateien ist nicht wirklich der interessante (und wichtige) Teil eines Compilers, daher

Kannst du dieses Geräusch hören? Es ist der Klang von tausend brillanten Theoremen, Anwendungen und Werkzeugen, die im automatentheoretischen Himmel 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 Computer-Vorgeschichte.Die sprachtheoretische Perspektive destilliert scheinbar komplizierte Fragen zu anspruchsvollen, undurchsichtigen Objekten in einfache Aussagen über Wörter und Bäume. Formale Sprachen spielen in der Informatik eine Rolle, die dem grundlegenden und bahnbrechenden Standpunkt entspricht, den Algebra und Topologie in die klassische Mathematik einbringen. 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 Assertionsverletzung? Respektiert ein Gerätetreiber bestimmte Protokolle bei der Interaktion mit dem Kernel? Das Verhalten eines Programms besteht aus einer Reihe von Ausführungen. mit anderen Worten, eine Sprache. Die Korrektheitseigenschaft ist eine andere Sprache. Das Problem mit der Programmkorrektheit führt zu einer Überprüfung der Spracheinbeziehung.
3. Kann Ihre Software in einer Endlosschleife stecken bleiben? Enthält ein verteilter Algorithmus ein Livelock? Wir brauchen Sprachen über unendliche Wörter, aber die Ansicht der Spracheinbeziehung gilt weiterhin.
4. Sie möchten ein Desinfektionsmittel erstellen, um schädliches Javascript zu erkennen, das in eine Webanwendung eingegeben wurde. Der Satz bösartiger Zeichenfolgen ist eine Sprache. Die Zeichenfolge, die in einer anderen Sprache in die Formulare eingegeben wurde. Sie möchten feststellen, ob der Schnittpunkt dieser Sprachen nicht leer ist.
5. Laufzeitüberwachung reaktiver und geschäftskritischer Systeme. Sie möchten einen Softwaremonitor entwerfen, der den Betrieb Ihres chemischen Prozesses überwacht oder Aktualisierungen einer Finanzdatenbank nachverfolgt. Dies sind Kernprobleme bei der Aufnahme und Überschneidung von Sprachen.
6. Mustererkennung mit ihren zahlreichen Anwendungen. Sie möchten Muster in Genomdaten, im 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 Sprachinferenzprobleme.
7. Bei einer Reihe von XML-Dokumenten möchten Sie ein Schema zurückentwickeln, das für diese Dokumente gilt. XML-Dokumente können als Bäume idealisiert werden. Ein Schema ist dann eine Spezifikation einer Baumsprache, und das Schema-Inferenzproblem ist ein Sprachinferenzproblem gegenüber Baumsprachen.
8. Viele Anwendungen erfordern automatisiertes arithmetisches Denken. Angenommen, wir legen eine logische Theorie wie die Presburger-Arithmetik fest, in der wir die natürlichen Zahlen, die Addition und das Prädikat weniger 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 Reihe von Wörtern; eine Sprache. Logische Operationen wie Konjunktion, Disjunktion und Negation werden zu Schnittmenge, Vereinigung und Ergänzung von Sprachen (existenzielle Quantifizierung ist eine Art Projektion).

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

Geben Sie Automaten ein. Mithilfe 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 wahnsinnigen Anzahl praktischer 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 erstaunlich ist das!

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

Kommentare

• haha, die Ironie

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 moderne Forschung, das auf die Automatentheorie zurückgeht, um ein modernes Konzept zu verstehen. In diesem Artikel beweisen Forscher, dass reguläre Sprachen alle Eigenschaftstester haben: „Normale 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) Modell, das beim Überlegen hilft, was kann und was noch wichtiger ist, was mit einigen Abfragesprachen nicht ausgedrückt werden kann. Einige interessante Ergebnisse sind:

• Ja, das berühmte Ergebnis ist, dass Deterministische endliche Automaten reguläre Sprachen erkennen – jetzt wissen Sie es Was Sie benötigen, um den Abgleich regulärer Ausdrücke zu implementieren.
• Pushdown-Automaten erkennen kontextfreie Grammatiken – jetzt haben Sie eine Vorstellung davon, wie ein Parser aussieht (oder zumindest eine große Klasse davon).
• Baumautomaten erkennt Anweisungen über monadische Logik zweiter Ordnung – jetzt haben Sie eine Vorstellung davon, was zur Implementierung einiger Programmiersprachen mit Einschränkungen erforderlich ist , oder … einige Anweisungen in SQL , zum Beispiel.

(und natürlich überspringe ich viel von anderen Klassen)

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

Wenn ich dies mit konkreten „weltlichen“ Werkzeugen in Verbindung bringen wollte, würde ich einen gemütlichen Morgen in der Bibliothek verbringen und ein paar Teile (AB?) aus Grundlagen von Datenbanken von Abiteboul & al und versucht, dies wieder mit Klassenmaterial zu verbinden. Natürlich ist es nur eine einer 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 die Automatentheorie in UG-Kursen den grundlegenden konzeptionellen Rahmen für die Einführung fortgeschrittener (und praktischer) Themen und auch um auf übersehene Zusammenhänge hinzuweisen; Zum Beispiel: Binäre Entscheidungsdiagramme (sie sind minimierte DFA; nach dem Unterrichten von DFA unterrichte ich häufig BDD-basiertes Lösen von Rätseln); Skripte, einschließlich in BioPerl und BioPython (und eine großartige Einstellung, um zu verstärken, wie viele unbeabsichtigte Übereinstimmungen in realen Skript-Regexps versteckt sein können), formales Debugging (Statuseigenschaften als negiertes FA, Überschneiden) und sogar VCR- oder Home-Intruder-Alarmprogrammierung (Alltagsstresssituation eines schlecht spezifizierten Automaten, der anhand unvollständiger Beispiele vermittelt wird; möglicherweise formalisiert durch Harels auf Szenarien basierende Synthese von Benutzeroberflächen). Ich verwende die Einstellung auch, um Pythons (fast) rein zu unterrichten funktionale Teilmenge, einschließlich Karten, Lambdas und Mengenverständnis, mit der Standard-FA-Algorithmen codiert werden können, oft auf eine Weise, die von mathematischen Definitionen praktisch nicht zu unterscheiden ist.

Kommentare

• Willkommen, Ganesh!
• Eine gute Art, Automaten zu unterrichten. Wären Sie bereit, Ihre Vorlesungsunterlagen zu teilen?

In Bezug auf die Automatentheorie wurden umfangreiche Forschungsarbeiten durchgeführt in der Modellprüfung in der Industrie verwendet. In Moshe Vardis jüngsten Vorlesungen am Fields Institute , insbesondere in der dritten Vorlesung „Logik, Automaten, Spiele und Algorithmen“, erfahren Sie, warum die Automatentheorie so ist immer noch wichtig und nützlich.

Zusammenfassung:

Der automatentheoretische Ansatz für Entscheidungsverfahren, eingeführt von Buechi, Elgot, Rabin und Trakhtenbrot in den 1950er und 1960er Jahren ist einer der grundlegendsten Ansätze für Entscheidungsverfahren. In jüngster 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 durch 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 Algorithmen über Automaten und Spiele.

Die Folien und Audiodateien der Vorlesungen finden Sie hier: 1 , 2 , 3 .

Ich werde eine andere Antwort aus einem ganz anderen praktischen Blickwinkel herauswerfen: Finite-State-Maschinen (oder zumindest einige einfache Verallgemeinerungen / Erweiterungen davon) werden häufig auf der KI verwendet Seite der Spielprogrammierung. Sie stellen sich als hervorragendes Modell für die Verkapselung des Charakterverhaltens heraus. 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 keinen 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 kontrastiert und die übereinander setzt, die Vollendung ist der Unwissenheit – dass es beweist, dass ein Mann mit den allerersten Elementen des Denkens nicht vertraut ist, und einen großen Beitrag dazu leistet, zu beweisen, dass sein Geist so pervers ist, dass er nicht in der Lage ist, sie zu unterrichten.

– James Mill (pseudonym als“ PQ”),“ Theorie und Praxis ”, London and Westminster Review , April 1836

Wir sollten die Semantik der Wörter „praktisch“ und „Anwendung“ berücksichtigen. Für einige Schüler ist praktisch 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 andere betonen, verwenden Sie Grammatiken beispielsweise beim Studium von Compilern. Aber noch mehr: Wenn Sie das gesamte Konzept verstehen, unterschiedliche Zustände und Regeln für Übergänge zwischen ihnen zu haben, können Sie ein besserer Programmierer werden, wenn Sie beispielsweise feststellen, dass Ihr Code hier und da redundant ist und wenn Sie ihn verbessern, Sie wenden in Ihrem Code dieselben konzeptionellen Ideen hinter der DFA-Minimierung an.

Ähnliches gilt für „Anwendung“. Was verstehst du unter diesem Wort? Selbst wenn Sie ein „bodenständiger Ingenieur“ sind, werden Sie Ideen sehen und verwenden, die denen der Automatentheorie in realen Projekten ähneln: Programmiercode, 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 endlicher Modelltheorie. Sicherlich werde ich das Pump-Lemma beim Einkaufen in einem Supermarkt wahrscheinlich nie verwenden müssen, aber solche Theoreme haben mir geholfen, die -Struktur bestimmter Sprachklassen, ganz zu schweigen von den logischen und algebraischen Strukturen, mit denen sie korrespondieren. Und das ist etwas, das ich mehr schätze als jedes Maß an Praktikabilität.

Zusammen mit der Logik können Automaten Möglichkeiten bieten, dies zu tun Überprüfen Sie Statistiken wie

$ \ qquad A \ models \ varphi $

auf einen Automaten $ A $ und eine Formel $ \ varphi $. Wenn $ A $ ein Modell eines Systems und $ \ varphi $ eine Formalisierung der gewünschten Eigenschaften ist, erhalten Sie eine Systemüberprüfung, ein sehr praktisches Problem mit einer wachsenden Anzahl von möglichen Anwendungen führt zu schönen Algorithmen. Wenn beispielsweise $ \ varphi $ eine LTL -Formel und $ A $ ein Büchi-Automat (dh ein unendlich laufender endlicher Automat) ist, können Sie $ \ varphi $ übersetzen zu einem äquivalenten Automaten $ A_ \ varphi $ und prüfen Sie, ob $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Endliche Automaten, die häufig als endliche Zustandsmaschinen in verschiedenen Kontexten oder mit ihren probabilistischen Varianten beschrieben werden. Hidden Markov-Modelle können zur Mustererkennung und Quantifizierung der Struktur eines Musters angewendet werden. Z.B. Was sind die kleinsten stochastischen endlichen Automaten, die mehr oder weniger Zeichenfolgen gemäß einer bestimmten Wahrscheinlichkeitsverteilung erzeugen oder statistische Eigenschaften einer Stichprobe von Zeichenfolgen (oder Zeitreihen) aus einer bestimmten Verteilung abgleichen?

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

Kommentare

• Um die praktische Seite zu erweitern, werden Hidden-Markov-Modelle bei der Spracherkennung verwendet Programme wie Kurzweil.

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

Einige haben großartige Antworten gegeben, wenn es um die Beziehung zur Industrie geht. Was wichtig sein sollte, ist ihr wissenschaftlicher Wert, und die Automatentheorie ist oft die Tür, um zuerst eine höhere Stufe der Berechnungstheorie zu verstehen im Studium eines Studenten. Die Automatentheorie hat eine große Anzahl von Theoremen, die in der Theoretischen Informatik überall auftauchen, insbesondere wenn man über Anwendungen wie Compiler sprechen möchte. Sein wissenschaftlicher Wert (es ist nicht veraltet, wie könnte es sein? Es ist die Kerntheorie auf diesem Gebiet.) Ist für jeden Wissenschaftler, der an Berechnungen interessiert ist, praktisch. Es ist praktisch, da es Wissen ist, das für diejenigen nützlich ist, die verstehen oder wollen Um die Natur der Berechnung zu verstehen. Wenn Sie darin keine Verwendung finden, stelle ich die Forschung in Frage oder beabsichtige sogar, CS zu studieren, da es keine Programmierung ist (das ist eine Anwendung von CS), sondern eine formale Wissenschaft.