Theorie der Automaten, endliche Automaten
Aufbau, Design und Funktionsprinzip verschiedener Maschinen werden maßgeblich von ihrem Funktionszweck bestimmt. Unterscheiden Sie zwischen Technologie-, Transport-, Computer-, Militär- und anderen Maschinen. Ganze automatische Komplexe zur Durchführung komplexer technologischer Prozesse sind in verschiedenen Branchen weit verbreitet. Es werden Automaten entworfen und gebaut, die verschiedene logische Funktionen ausführen (logische Maschinen).
Theorie der Automaten — Abschnitt Kybernetik, die unter dem Einfluss der Anforderungen der Technologie digitaler Computer und Steuerungsmaschinen entstand. Diskrete Automaten, die in der Automatentheorie untersucht werden, sind abstrakte Modelle realer Systeme (sowohl technischer als auch biologischer), die diskrete (digitale) Informationen in diskreten Zeitschritten verarbeiten.
Die Automatentheorie basiert auf präzisen mathematischen Konzepten, die intuitive Vorstellungen über die Funktionsweise (das Verhalten) des Automaten und über seine Struktur (interne Struktur) formalisieren.
Dabei wird unter Informationstransformation immer eine Operation verstanden, die Eingabesequenzen bestehend aus Buchstaben des Eingabealphabets in Ausgabesequenzen bestehend aus Buchstaben des Ausgabealphabets umwandelt.
Der Apparat der mathematischen Logik, Algebra, Wahrscheinlichkeitstheorie, Kombinatorik und Graphentheorie ist weit verbreitet.
Das Problem mit der Automatentheorie in einigen ihrer Teile (Strukturtheorie der Automaten) nahm zu aus der Theorie der Relaiskontaktschaltungen, die Ende der 1930er Jahre Gestalt annahm. inklusive Methoden der logischen Algebra.
In der Strukturtheorie von Automaten werden verschiedene Arten von Schemata untersucht, die beschreiben sollen, wie ein komplexer Automat aus einfacheren Komponenten (Elementen) erstellt wird, die ordnungsgemäß in einem System verbunden sind.
Eine andere Richtung, die sogenannte abstrakte Automatentheorie, untersucht das Verhalten von Automaten (d. h. die Art der von ihnen durchgeführten Informationstransformation), abstrahiert dabei von den Besonderheiten ihrer inneren Struktur und entstand in den 1950er Jahren.
Im Rahmen der abstrakten Automatentheorie erschöpft sich der Inhalt der Begriffe „Automat“ und „Maschine“ im Wesentlichen in der Standardbeschreibung der Informationstransformation, die ein Automat durchführt. Eine solche Transformation kann deterministischer, aber auch probabilistischer Natur sein.
Am meisten untersucht werden deterministische Maschinen (Automaten), zu denen endliche Automaten gehören – der Hauptgegenstand der Automatentheorie.
Eine endliche Zustandsmaschine zeichnet sich durch eine begrenzte Speichermenge (die Anzahl interner Zustände) aus und wird mithilfe einer Übergangsfunktion definiert.Mit einiger vernünftiger Idealisierung können alle modernen mathematischen Maschinen und sogar das Gehirn im Hinblick auf ihre Funktionsweise als endliche Automaten betrachtet werden.
Die Begriffe „sequentielle Maschine“, „Milly-Automat“, „Moore-Automat“ werden in der Literatur (und nicht einheitlich von allen Autoren) als Synonyme des Begriffs „endlicher Automat“ oder zur Hervorhebung bestimmter Merkmale in den Übergangsfunktionen eines endlichen verwendet Automat.
Automaten mit unbegrenztem Speicher sind Turing-Maschinen, die (potenziell) jede effiziente Informationstransformation durchführen können. Das Konzept der „Turingmaschine“ entstand früher als das Konzept der „Finite-State-Maschine“ und wird hauptsächlich in der Algorithmentheorie untersucht.
Die abstrakte Automatentheorie steht in engem Zusammenhang mit bekannten algebraischen Theorien, beispielsweise der Halbgruppentheorie. Aus angewandter Sicht sind die Ergebnisse von Interesse, die die Transformation von Informationen in einem Automaten hinsichtlich der Speichergröße charakterisieren.
Dies ist beispielsweise bei Problemen mit Experimenten an Automaten (Werke von E.F. Moore usw.) der Fall, bei denen aus den Ergebnissen die eine oder andere Information über die Übergangsfunktionen des Automaten oder über die Kapazität seines Speichers gewonnen wird Experimente.
Eine weitere Aufgabe besteht darin, die Perioden der Ausgabesequenzen zu berechnen, basierend auf den verfügbaren Informationen über die Speichergröße des Automaten und die Perioden der Eingabesequenzen.
Von großer Bedeutung ist die Entwicklung von Methoden zur Minimierung des Speichers endlicher Automaten und zur Untersuchung ihres Verhaltens in zufälligen Umgebungen.
In der abstrakten Automatentheorie ist das Syntheseproblem das folgende.In einer klar formalisierten Sprache werden die Bedingungen für das Verhalten des entworfenen Automaten (für das im Automaten dargestellte Ereignis) geschrieben. In diesem Fall ist es notwendig, Methoden zu entwickeln, die entsprechend jeder schriftlichen Bedingung:
1) Finden Sie heraus, ob es eine solche Zustandsmaschine gibt, dass die von ihr umgewandelten Informationen diese Bedingung erfüllen;
2) Wenn ja, dann werden die Übergangsfunktionen einer solchen endlichen Zustandsmaschine konstruiert oder ihre Speichergröße geschätzt.
Die Lösung des Syntheseproblems in einer solchen Formulierung setzt die vorläufige Erstellung einer geeigneten Sprache zur Aufzeichnung der Betriebsbedingungen eines Automaten mit geeigneten Algorithmen für den Übergang von der Aufzeichnung zu transitiven Funktionen voraus.
In der Strukturtheorie von Automaten besteht das Syntheseproblem darin, eine Kette von Elementen eines gegebenen Typs zu konstruieren, die einen durch seine Übergangsfunktionen gegebenen endlichen Automaten realisiert. In diesem Fall geben sie normalerweise ein Optimalitätskriterium an (z. B. die Mindestanzahl von Elementen) und versuchen, ein optimales Schema zu erhalten.
Wie sich später herausstellte, bedeutet dies, dass einige der früher in Bezug auf Relaiskontaktschaltungen entwickelten Methoden und Konzepte auf Schaltungen eines anderen Typs anwendbar sind.
Im Zusammenhang mit der Entwicklung elektronischer Technologien sind die Systeme am weitesten verbreitet von Funktionselementen (logische Netzwerke). Ein Sonderfall logischer Netze sind abstrakte neuronale Netze, deren Elemente Neuronen genannt werden.
Abhängig von der Art der Schaltkreise und der Informationsumwandlung, für die sie bestimmt sind, wurden viele Synthesemethoden entwickelt (Synthese von Relaisgeräten).
Sehen -Minimierung kombinatorischer Schaltkreise, Carnot-Karten, Schaltkreissynthese
Endlicher Zustandsautomat — ein mathematisches Modell eines Steuerungssystems mit einer festen Speichergröße (die sich während des Betriebs nicht vergrößern kann).
Das Konzept einer endlichen Zustandsmaschine ist eine mathematische Abstraktion, die die allgemeinen Eigenschaften einer Reihe von Steuerungssystemen (z. B. eines Mehrschleifen-Relaisgeräts) charakterisiert. Alle diese Systeme haben gemeinsame Merkmale, die natürlich als Definition eines endlichen Automaten akzeptiert werden.
Jeder fertige Automat verfügt über einen Eingang, der äußeren Einflüssen und inneren Elementen ausgesetzt ist. Sowohl für Eingabeelemente als auch für interne Elemente gibt es eine feste Anzahl diskreter Zustände, die sie annehmen können.
Die Änderung der Zustände der Eingabe- und internen Elemente erfolgt zu diskreten Zeitpunkten, deren Intervalle als Ticks bezeichnet werden. Der interne Zustand (der Zustand der Interna) am Ende des Bandes wird vollständig durch den internen Zustand und den Zustand der Eingabe am Anfang des Bandes bestimmt.
Alle anderen Definitionen eines endlichen Automaten können auf dieses Merkmal reduziert werden, insbesondere Definitionen, die davon ausgehen, dass ein endlicher Automat eine Ausgabe hat, die vom internen Zustand des Automaten zu einem bestimmten Zeitpunkt abhängt.
Im Hinblick auf ein solches Merkmal ist die Art seiner Eingaben und internen Zustände für die Beschreibung eines vollständigen Automaten irrelevant. Anstelle von Eingaben und Zuständen können Sie sich auch einfach deren Zahlen in einer Zufallsnummerierung ansehen.
Der Zustandsautomat wird gesetzt, wenn die Abhängigkeit seiner internen Zustandsnummer von der vorherigen internen Zustandsnummer und der vorherigen Eingangszustandsnummer angegeben ist. Eine solche Aufgabe kann in Form eines Abschlusstisches erfolgen.
Eine weitere gängige Methode zur Definition eines vollständigen Automaten ist die Konstruktion des sogenannten Übergangsdiagramme. Eingabezustände werden oft einfach als Eingaben bezeichnet, und interne Zustände sind einfach Zustände.
Eine endliche Zustandsmaschine kann ein Modell sowohl für technische Geräte als auch für einige biologische Systeme sein. Automaten der ersten Art sind beispielsweise Relaisgeräte und verschiedene elektronische Computer, inkl. speicherprogrammierbare Steuerungen.
Im Falle eines Relaisgeräts spielen Kombinationen von Zuständen der empfindlichen Elemente des Relaisgeräts die Rolle der Eingangszustände (jede Kombination solcher Zustände ist ein „komplexer Zustand“, der durch die Angabe aller empfindlichen Elemente gekennzeichnet ist). diese diskreten Zustände, die sie in einem bestimmten Moment haben). Ebenso fungieren Zustandskombinationen von Zwischenelementen eines Relaisgeräts als interne Zustände.
Eine speicherprogrammierbare Steuerung (SPS) ist ein Beispiel für ein Gerät mit Relaiswirkung, das als eigenständige Zustandsmaschine bezeichnet werden kann.
Sobald das Programm in die SPS eingegeben wurde und die Steuerung mit der Berechnung begonnen hat, ist es nämlich keinen äußeren Einflüssen mehr ausgesetzt und jeder nachfolgende Zustand wird vollständig durch seinen vorherigen Zustand bestimmt. Wir können davon ausgehen, dass der Eingang in jedem Taktzyklus den gleichen Zustand hat.
Umgekehrt wird jeder endliche Automat, der den einzig möglichen Eingabezustand hat, natürlich als autonom bezeichnet, da in diesem Fall die externe Umgebung keine Informationen enthält, die sein Verhalten steuern.
Siehe auch:
Der Einsatz von Mikroprozessorsystemen in der Elektrotechnik am Beispiel des Einsatzes von SPS