Gibt es unendliche Automaten?

In der Automatentheorie lesen wir alle Automaten von Anfang an als endliche Automaten. Ich möchte wissen, warum Automaten endlich sind. Um klar zu sein, was ist in einem Automaten endlich - das Alphabet, die Sprache, Zeichenketten mit regulären Ausdrücken oder was? Und gibt es (theoretisch) unendliche Automaten?

Alle Automatenmodelle, denen Sie normalerweise begegnen, sind endlich dargestellt. Andernfalls wären es unzählige, was bedeutet, dass sie nicht von Turing-complete-Modellen erfasst werden. Oder in CS-think wären sie nutzlos¹.

"Endliche Automaten" werden als endlich bezeichnet, da sie nur eine endliche Menge von Konfigurationen haben (die Eingabezeichenfolge beiseite). Zum Beispiel haben Pushdown-Automaten einen Stapel, der beliebigen Inhalt haben kann - es gibt unendlich viele mögliche Konfigurationen.

Hinweis: Konfigurationen von PDAs sind immer noch endlich vertreten! Tatsächlich muss jedes Rechenmodell, das in die Turing-Berechenbarkeit fällt, endlich darstellbare Konfigurationen haben, sonst könnten TMs sie nicht simulieren.

1. Ich vernachlässige hier die Hyperberechnung bewusst, um diese Frage zu beantworten.

Der vollständige Name lautet "endlicher Zustand" ". Der entscheidende Teil ist, dass der Zustand des Automaten vollständig durch ein Element einer endlichen Menge diskreter Zustände charakterisiert werden kann. Das heißt, wenn der (relevante) Zustand des Automaten eine reelle Variable enthält, gibt es unendlich viele mögliche Zustände (abgesehen von der Endlichkeit von Gleitkommadarstellungen), und der Automat ist nicht endlich.

In der theoretischen Informatik mag dies nie vorkommen, im Bereich der Modellierung reeller Zahlenfolgen ist dies jedoch nicht zu exotisch. Mit Hidden-Markov-Modellen kann eine Zahlenfolge als Ausgabe eines Wahrscheinlichkeitssystems modelliert werden, das aus einem Ausgabefilter für jeden Zustand eines (diskreten, endlichen) Markov-Modells mit nicht beobachtbaren Zuständen besteht. Die Filter berechnen die nächste reelle Ausgabe aus einem Vektor der vorherigen Ausgaben ("autoregressives" Modell), aber das zugrunde liegende Markov-Modell ist endlich, da seine Übergangswahrscheinlichkeiten nur vom aktuellen Markov-Zustand abhängen.

In diesem Artikel ( Volltext ) wird jedoch eine Variation entwickelt, bei der die Übergangswahrscheinlichkeiten auch vom reellen Zahlenvektor früherer Ausgaben abhängen. Der Zustand dieses Systems ist die Kombination eines diskreten Markov-Zustands und eines Tupels reeller Zahlen ("Mixed-State-Markov-Modell"), daher kann es sich in einer unendlichen Anzahl verschiedener Zustände befinden.

Kurz gesagt, unendliche Automaten sind theoretisch gut definiert und gelegentlich sogar anzutreffen.

In einem endlichen Automaten gibt es einiges an Endlichkeit: die Anzahl der Zustände, die Größe des zugrunde liegenden Alphabets und die Länge der Zeichenfolgen, die von der Maschine akzeptiert werden.

Sie können die Endlichkeitsbedingung auf diesen sicherlich lockern, indem Sie beispielsweise zulassen, dass die Maschine unendlich viele Zustände hat, aber wenn Sie dies tun, wird die resultierende Maschine in dem Sinne uninteressant, dass solche Maschinen so entworfen werden können, dass sie überhaupt alle Sprachen akzeptieren.

Tatsächlich gibt es in der Automatentheorie (die viel von den Ursprüngen von Kleene, Rabin und Scott abweicht) viele Formen von Automaten, die nicht endlich sind. Dies ergibt sich aus mehreren Gründen.

Pushdown-Automaten sind beispielsweise Automaten mit einer unendlichen Anzahl von Konfigurationen (diese haben eine endliche Anzahl von Zuständen, aber in Wirklichkeit sollten diese als "unendliche Automaten" betrachtet werden).

Ebenso gibt es andere Beispiele für unendliche Automaten, für die der Zustandsraum unendlich ist, aber sehr strukturiert. Zum Beispiel betrachtet man die Klasse von Automaten, die als Zustandsraum einen (endlichen) Vektorraum haben, und als Übergangsfunktionen lineare Abbildungen (plus einige anfängliche und letzte Dinge). Diese sind als gewichtete Automaten über einem Basisfeld bekannt (nach Schützenberger in 61). Diese können minimiert und auf Gleichheit geprüft werden. Andere Beispiele sind Registerautomaten (diese Automaten haben eine endliche Menge von Registern und arbeiten über ein unendliches Alphabet: Diese können Buchstaben mit Registern vergleichen und Buchstaben in Registern speichern) und die modernere Form von nominalen Automaten(die die gleiche Ausdruckskraft haben, aber bessere Grundlagen und Eigenschaften haben). Die Leere solcher Automaten ist entscheidend.

$A^*$$a$$u$$ua$, und ein Staat akzeptiert, wenn er zu L) gehört. Es gibt auch ein letztes Objekt (das Sprachen als Zustände hat!). Die Existenz dieser beiden Objekte ist eine Möglichkeit, auf hoher Ebene zu erklären, warum deterministische Automaten minimiert werden können und eng mit der Myhill-Nerode-Kongruenz verknüpft sind.

Abschließend gibt es unendlich viele Automaten, aber die Modelle, die zuerst in einer Vorlesung untersucht werden, sind immer die endlichen.

Ich denke, die Frage geht davon aus, dass es keine Automaten mit unendlichen Zuständen gibt, die es einfach nicht wert sind, erwähnt zu werden.

In der Automatentheorie gibt es eine Hierarchie der Kräfte verschiedener virtueller Modelle. Die eine, die ich gelernt habe, hatte 4 (ich erinnere mich, dass es einige Zeit her ist), die eine, die ich bei Wikipedia gefunden habe, hat 5. Die schwächste in beiden Automaten mit endlichen Zuständen und die stärkste ist Turing-Maschinen. Es gibt ein Konzept für ein Level, das leistungsfähiger ist als Turing-Maschinen und das man locker Hypercomputing nennt. Viele verschiedene Beschreibungen von virtuellen Maschinen fallen in eine dieser Ebenen. Turingmaschinen sind insbesondere für zahlreiche Modelle bekannt, die alle die gleiche Rechenleistung haben.

In eine dieser Ebenen fallen unendliche Zustandsautomaten, von denen mindestens eine formal definiert ist. Es mag etwas Interessantes sein, zu zeigen, wie eine bestimmte strenge Definition eines Endlosautomaten in eine dieser Ebenen passt, aber ansonsten wäre es nicht von Nutzen, wenn es viel besser untersuchte virtuelle Maschinen gibt, die jede Ebene repräsentieren . Es ist ähnlich wie das geringe Interesse an einer milliardenschweren Band-Turing-Maschine, da sie nicht leistungsfähiger als eine einzelne Band-Turing-Maschine wäre, aber komplizierter in der Handhabung.

Nun, wenn Sie zufällig ein Automatensystem mit unendlichen Zuständen gefunden haben, das nicht mit einer vorhandenen Hierarchieebene übereinstimmt, könnte dies interessant sein. Aber ohne das werden unendliche Zustandsautomaten bereits in der bestehenden Hierarchie erfasst, und angesichts der zusätzlichen Komplikationen beim Umgang mit der Unendlichkeit vermeiden wir sie genauso, wie wir jedes übermäßig komplizierte Turing-Maschinenmodell vermeiden.

Die (naive) unendliche Version der deterministischen Zustandsmaschine ist zu mächtig . So etwas wäre in der Lage, sich jede Sprache zu "merken", daher gibt es nicht viel zu lernen, wenn man sie in Betracht zieht.

Betrachten Sie beispielsweise über einem binären Alphabet einen Automaten in Form eines vollständigen binären Baums von unendlicher Höhe. Jede mögliche Zeichenfolge, die Sie als Eingabe betrachten könnten, entspricht eindeutig einem Knoten des Baums, sodass Sie für jede Sprache eine Entscheidung treffen können, indem Sie die entsprechenden Knoten einfach dazu bringen, Zustände zu akzeptieren.