Was sind die endlichen Automaten? [geschlossen]
Was nützt endliche Automaten ? Und alle Konzepte, die wir in der Theorie der Berechnung studieren. Ich habe ihre Anwendungen noch nie gesehen.
9 Antworten
Sie sind die theoretischen Grundlagen von Konzepten, die in der Informatik und Programmierung weit verbreitet sind, und ihr Verständnis hilft Ihnen, besser zu verstehen, wie man sie benutzt (und was ihre Grenzen sind). Die drei grundlegenden, denen Sie begegnen sollten, sind in zunehmender Reihenfolge der Macht:
- Finite Automaten, die regulären Ausdrücken entsprechen. Reguläre Ausdrücke werden häufig zum Programmieren von Zeichenfolgen und zum Extrahieren von Text verwendet. Sie sind eine einfache Methode zur Beschreibung einer Menge gültiger Strings unter Verwendung von Grundzeichen, Gruppierung und Wiederholung. Sie können viel tun, aber sie können keine ausgewogenen Klammern setzen.
- Push-down-Automaten, äquivalent zu kontextfreien Grammatiken. Text- / Eingabe-Parser und -Compiler verwenden diese, wenn reguläre Ausdrücke nicht stark genug sind (und eines der Dinge, die Sie beim Studium endlicher Automaten lernen, ist, was reguläre Ausdrücke nicht können, was entscheidend ist, wann und wann ein regulärer Ausdruck geschrieben werden muss etwas komplizierter zu verwenden). Kontextfreie Grammatiken können "Sprachen" (Sätze von gültigen Strings) beschreiben, bei denen die Gültigkeit an einem bestimmten Punkt beim Parsen der Strings nicht davon abhängt, was sonst noch gesehen wurde.
- Turing-Maschinen, äquivalent zu allgemeinen Berechnungen (alles, was Sie mit einem Computer tun können). Einige der Dinge, die Sie lernen, wenn Sie diese abdecken, ermöglichen es Ihnen, die Grenzen der Datenverarbeitung selbst zu verstehen. Ein guter Theoriekurs wird Sie über das Halteproblem informieren, mit dem Sie Probleme identifizieren können, für die es unmöglich ist, ein Programm zu schreiben. Sobald Sie ein solches Problem erkannt haben, wissen Sie, dass Sie aufhören sollten es zu versuchen (oder es zu etwas zu verfeinern, was möglich ist).
Wenn Sie die Theorie und die Grenzen dieser verschiedenen Computermechanismen verstehen, können Sie Probleme und Programme besser verstehen und mehr über Programmierung nachdenken.
Vor etwa einem Jahr wurde auf einer der freiberuflichen Coding-Tauschbörsen eine Bitte um Arbeit veröffentlicht, in der im Wesentlichen nach einem Programm gefragt wurde, das das Halteproblem löste. Mehrere Personen antworteten mit Angeboten, sie "verstanden die Anforderungen" und könnten "sofort starten". Es war unmöglich, ein Programm zu schreiben, das den Anforderungen entsprach. Wenn man die Computertheorie versteht, kann man nicht derjenige sein, der in der Öffentlichkeit demonstriert, dass er das Rechnen wirklich nicht versteht (und sich nicht darum kümmert, ein Problem gründlich zu untersuchen, bevor man Verständnis erklärt und ein Angebot macht).
Jede GUI, jeder Workflow kann als endlicher Automat behandelt werden. Stellen Sie sich jede Seite als einen Zustand und Übergänge vor, die aufgrund bestimmter Ereignisse auftreten. Vielleicht können Sie nicht zu einer bestimmten Seite oder der nächsten Stufe des Workflows übergehen, bis eine Reihe von Bedingungen erfüllt sind.
Zum Beispiel um Zustände einiger Objekte mit definiertem Lebenszyklus zu verwalten. Als Beispiel dafür: Bestellungen im Buchladen. Ein Auftrag kann folgende Zustände haben: -bestellt - bezahlt -Versand -done
und Programm der endlichen Automaten weiß, wie ein Zustand durch andere geändert werden kann.
Endliche Automaten sind z.B. verwendet, um formale Sprachen zu analysieren. Dies bedeutet, dass endliche Automaten bei der Erstellung von Compiler- und Interpretertechniken sehr nützlich sind.
Historisch gesehen hat die endliche Zustandsmaschine gezeigt, dass viele Probleme durch einen sehr einfachen Automaten gelöst werden können.
Der endliche Automat ist eine Art von Zustandsmaschine (SM). Im Allgemeinen werden SMs verwendet, um formale Sprachen zu analysieren.
Sie können als formale Sprache viele Entitäten verwenden, nicht nur Zeichen.
Und normale Sprache ist eine Art von formeller Sprache. Es gibt einige Theorien, die zeigen, welche Art von SM besser ist, um eine reguläre Sprache zu parsen: Ссылка
Einige Anwendungen von endlichen Automaten:
String-Verarbeitung
Sie sollten alle Vorkommen einer kurzen Zeichenfolge (Musterzeichenfolge) in einer langen Zeichenfolge (Textzeichenfolge) finden. Dies kann durch Verarbeiten des Texts über ein DFA erfolgen: das DFA für alle Zeichenfolgen, die mit der Musterzeichenfolge enden. Jedes Mal, wenn der Annahmestatus erreicht ist, wird die aktuelle Position im Text ausgegeben.
Beispiel :
Auffinden von 1001 Um alle Vorkommen von Muster 1001 zu finden, con
Strukturiere das DFA für alle Strings, die auf 1001 enden.
Endliche Automaten
Ein endlicher Automat ist ein FA zusammen mit Aktionen auf den Bögen. Ein triviales Beispiel für eine Kommunikationsverbindung:
Beispiel FSM: Bot-Verhalten Ein Bot ist ein computergenerierter Charakter in einem Videospiel.
Beachten Sie, dass die Verwendung von endlichen Automaten die Automatisierung ermöglicht.
Zustandsdiagramme
State-Charts modellieren Aufgaben als eine Reihe von Zuständen und Aktionen. Sie erweitern FA-Diagramme.
Hier ist ein vereinfachtes Zustandsdiagramm für eine Stoppuhr.
Tags und Links theory finite-automata