Die Übergangstabelle ist im Grunde eine tabellarische Darstellung der Übergangsfunktion. Es benötigt zwei Argumente (einen Zustand und ein Symbol) und gibt einen Zustand (den „nächsten Zustand“) zurück.
Eine Übergangstabelle wird durch die folgenden Dinge dargestellt:
- Spalten entsprechen Eingabesymbolen.
- Zeilen entsprechen Zuständen.
- Einträge entsprechen dem nächsten Zustand.
- Der Startzustand wird durch einen Pfeil ohne Quelle gekennzeichnet.
- Der Akzeptanzzustand wird durch einen Stern gekennzeichnet.
Beispiel 1:
Lösung:
Die Übergangstabelle des gegebenen DFA lautet wie folgt:
| Gegenwärtiger Zustand | Nächster Zustand für Eingang 0 | Nächster Status von Eingabe 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Erläuterung:
- In der obigen Tabelle zeigt die erste Spalte alle aktuellen Zustände an. Unter Spalte 0 und 1 werden die nächsten Zustände angezeigt.
- Die erste Zeile der Übergangstabelle kann folgendermaßen gelesen werden: Wenn der aktuelle Zustand q0 ist, ist der nächste Zustand am Eingang 0 q1 und am Eingang 1 der nächste Zustand q2.
- Wenn in der zweiten Zeile der aktuelle Zustand q1 ist, ist bei Eingang 0 der nächste Zustand q0 und bei Eingang 1 ist der nächste Zustand q2.
- Wenn in der dritten Zeile der aktuelle Zustand q2 am Eingang 0 ist, ist der nächste Zustand q2, und am Eingang 1 ist der nächste Zustand q2.
- Der mit q0 markierte Pfeil zeigt an, dass es sich um einen Startzustand handelt, und der mit q2 markierte Kreis zeigt an, dass es sich um einen Endzustand handelt.
Beispiel 2:
Lösung:
Die Übergangstabelle der gegebenen NFA lautet wie folgt:
| Gegenwärtiger Zustand | Nächster Zustand für Eingang 0 | Nächster Status von Eingabe 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Erläuterung:
- Die erste Zeile der Übergangstabelle kann folgendermaßen gelesen werden: Wenn der aktuelle Zustand q0 ist, ist der nächste Zustand am Eingang 0 q0 und am Eingang 1 der nächste Zustand q1.
- Wenn in der zweiten Zeile der aktuelle Zustand q1 ist, ist der nächste Zustand bei Eingang 0 entweder q1 oder q2, und bei Eingang 1 ist der nächste Zustand q2.
- Wenn in der dritten Zeile der aktuelle Status q2 am Eingang 0 ist, ist der nächste Status q1, und am Eingang 1 ist der nächste Status q3.
- Wenn in der vierten Zeile der aktuelle Zustand q3 am Eingang 0 ist, ist der nächste Zustand q2, und am Eingang 1 ist der nächste Zustand q2.