Zustandsübergangstabelle - State-transition table
In der Automatentheorie und sequentiellen Logik ist eine Zustandsübergangstabelle eine Tabelle, die zeigt, in welchen Zustand (oder Zustände im Fall eines nichtdeterministischen endlichen Automaten ) sich ein endlicher Automat basierend auf dem aktuellen Zustand und anderen Eingaben bewegt. Es ist im Wesentlichen eine Wahrheitstabelle, in der die Eingaben den aktuellen Zustand zusammen mit anderen Eingaben enthalten und die Ausgaben den nächsten Zustand zusammen mit anderen Ausgaben umfassen.
Eine Zustandsübergangstabelle ist eine von vielen Möglichkeiten, einen endlichen Automaten zu spezifizieren. Andere Möglichkeiten umfassen ein Zustandsdiagramm .
Gängige Formen
Eine Dimension
Zustandsübergangstabellen sind manchmal eindimensionale Tabellen, auch Merkmalstabellen genannt . Sie ähneln eher Wahrheitstafeln als ihrer zweidimensionalen Form. Die einzelne Dimension zeigt Eingänge, aktuelle Zustände, nächste Zustände und (optional) Ausgänge an, die den Zustandsübergängen zugeordnet sind.
| Eingang | Aktuellen Zustand | Nächstes Bundesland | Ausgabe |
|---|---|---|---|
| ich 1 | S 1 | S ich | O x |
| ich 2 | S 1 | S j | Oh ja |
| … | … | … | … |
| ich nein | S 1 | S k | O z |
| ich 1 | S 2 | S ich′ | O x′ |
| ich 2 | S 2 | S j′ | Oh ja |
| … | … | … | … |
| ich nein | S 2 | S k′ | O z′ |
| … | … | … | … |
| ich 1 | S m | S ich″ | O x″ |
| ich 2 | S m | S j″ | Oh ja |
| … | … | … | … |
| ich nein | S m | S k″ | O z″ |
Zwei Dimensionen
Zustandsübergangstabellen sind typischerweise zweidimensionale Tabellen. Es gibt zwei gängige Möglichkeiten, sie anzuordnen.
In erster Linie zeigt eine der Dimensionen aktuelle Zustände an, während die andere Eingaben anzeigt. Die Zeilen-/Spalten-Schnittpunkte zeigen nächste Zustände und (optional) Ausgaben an, die den Zustandsübergängen zugeordnet sind.
|
Eingang
Aktuellen Zustand
|
ich 1 | ich 2 | … | ich nein |
|---|---|---|---|---|
| S 1 | S i /O x | S j /O y | … | S k /O z |
| S 2 | S i′ /O x′ | S j′ /O y′ | … | S k′ /O z′ |
| … | … | … | … | … |
| S m | S i″ /O x″ | S j″ /O z″ | … | S k″ /O z″ |
Zweitens zeigt eine der Dimensionen aktuelle Zustände an, während die andere die nächsten Zustände anzeigt. Die Zeilen-/Spalten-Schnittpunkte zeigen Eingänge und (optional) Ausgänge an, die den Zustandsübergängen zugeordnet sind.
|
Nächstes Bundesland
Aktuellen Zustand
|
S 1 | S 2 | … | S m |
|---|---|---|---|---|
| S 1 | Ich i / O x | — | … | — |
| S 2 | — | — | … | ich j / O ja |
| … | … | … | … | … |
| S m | — | I k /O z | … | — |
Andere Formen
Gleichzeitige Übergänge in mehreren endlichen Automaten können in einer effektiven n-dimensionalen Zustandsübergangstabelle gezeigt werden, in der Zeilenpaare (Sätze von) aktuellen Zuständen auf nächste Zustände abbilden. Dies ist eine Alternative zur Darstellung der Kommunikation zwischen separaten, voneinander abhängigen endlichen Automaten.
Im anderen Extrem wurden für jeden der Übergänge innerhalb eines einzigen endlichen Automaten separate Tabellen verwendet: "UND/ODER-Tabellen" ähneln unvollständigen Entscheidungstabellen, bei denen die Entscheidung für die vorhandenen Regeln implizit die Aktivierung von der dazugehörige Übergang.
Beispiel
Ein Beispiel für eine Zustandsübergangstabelle zusammen mit dem entsprechenden Zustandsdiagramm für einen endlichen Automaten ist unten aufgeführt:
|
Eingang
Aktuellen Zustand
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | S 1 | S 2 |
|
In der Zustandsübergangstabelle werden alle möglichen Eingaben zum endlichen Automaten über die Spalten der Tabelle aufgezählt, während alle möglichen Zustände über die Zeilen hinweg aufgezählt werden. Befindet sich die Maschine im Zustand S 1 (erste Zeile) und erhält eine Eingabe von 1 (zweite Spalte), bleibt die Maschine im Zustand S 1 . Befindet sich die Maschine nun im Zustand S 1 und erhält eine Eingabe von 0 (erste Spalte), geht die Maschine in den Zustand S 2 über .
Ersteres ist im Zustandsdiagramm durch den mit 1 gekennzeichneten Pfeil von S 1 nach S 1 gekennzeichnet, letzteres durch den mit 0 gekennzeichneten Pfeil von S 1 nach S 2. Dieser Vorgang lässt sich statistisch beschreiben mit Markov-Ketten .
Bei einem nichtdeterministischen endlichen Automaten kann eine Eingabe dazu führen, dass sich der Automat in mehr als einem Zustand befindet, daher sein Nicht-Determinismus . Dies wird in einer Zustandsübergangstabelle durch die Menge aller Zielzustände gekennzeichnet, die in geschweifte Klammern {} eingeschlossen sind. Ein Beispiel für eine Zustandsübergangstabelle zusammen mit dem entsprechenden Zustandsdiagramm für einen nichtdeterministischen endlichen Automaten ist unten angegeben:
|
Eingang
Aktuellen Zustand
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | {S 1 , S 2 } | S 2 |
|
Befindet sich die Maschine im Zustand S 2 und erhält eine Eingabe von 0, befindet sich die Maschine gleichzeitig in zwei Zuständen, den Zuständen S 1 und S 2 .
Transformationen vom/zum Zustandsdiagramm
Es ist möglich, ein Zustandsdiagramm aus einer Zustandsübergangstabelle zu zeichnen . Nachfolgend finden Sie eine Abfolge von einfach zu befolgenden Schritten:
- Zeichnen Sie die Kreise, um die angegebenen Zustände darzustellen.
- Scannen Sie für jeden der Zustände die entsprechende Zeile und zeichnen Sie einen Pfeil zu dem/den Zielzustand(en). Es kann mehrere Pfeile für ein Eingabezeichen geben, wenn der endliche Automat nicht deterministisch ist.
- Legen Sie einen Zustand als Startzustand fest . Der Startzustand ist in der formalen Definition eines endlichen Automaten angegeben.
- Legen Sie einen oder mehrere Zustände als Annahmezustand fest . Dies ist auch in der formalen Definition eines endlichen Automaten gegeben.
Siehe auch
- Nachbarschaftsliste
- Adjazenzmatrix
- Anregungstabelle
- Endlicher Automat
- Moore-Maschine
- Mehlige Maschine
Verweise
Weiterlesen
- Michael Sipser: Einführung in die Rechentheorie . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X