/ Compilerbau & Formale Sprachen

DFA Zustandsübergänge

Maximale Anzahl Zustandsübergänge eines deterministischen endlichen Automaten: Übergaenge = Zustaende · Alphabet (|δ| = |Q|·|Σ|).

01 · Eingabe

DFA Zustandsübergänge berechnen

Maximale Anzahl Zustandsübergänge eines deterministischen endlichen Automaten: Übergaenge = Zustaende · Alphabet (|δ| = |Q|·|Σ|).

Lösen für

Übergaenge = Zustaende · Alphabet

Zustaende Zustandsanzahl

Alphabet Alphabetgröße

Worum geht es?

Ein deterministischer endlicher Automat (DFA) ist über δ : Q × Σ → Q definiert. Bei einer vollständigen Übergangsfunktion ist für jedes Paar (q, a) genau ein Folgezustand definiert — die Übergangstabelle besitzt deshalb genau |Q| · |Σ| Einträge.

Diese Zahl bestimmt den Speicherbedarf der Übergangstabelle eines Lexers und ist die Grundlage für Schätzungen bei der DFA-Minimierung sowie für die Tabellengröße der ausgegebenen case-Sprünge.

Die Formel

Formel DFA-Übergangsfunktion

Übergaenge = Zustaende · Alphabet

Umstellungen:
    Zustaende = Übergaenge / Alphabet
    Alphabet  = Übergaenge / Zustaende

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
Zustaende	Zustandsanzahl	—	Anzahl Zustände \|Q\| im DFA.
Alphabet	Alphabetgröße	—	Anzahl Eingabesymbole \|Σ\|.
Übergaenge	Übergänge	—	Einträge in der Übergangstabelle \|δ\|.

Minimal-Beispiel

DFA für gerade Bits mit |Q| = 2 und |Σ| = 2:

Rechnung Mini-DFA

Übergaenge = 2 · 2
           = 4

Praxis-Beispiele

Beispiel 1 — Bezeichner-Erkenner

Ein Lexer-DFA mit |Q| = 12 Zuständen über ASCII-Druckzeichen (|Σ| = 95):

Rechnung Bezeichner

Übergaenge = 12 · 95
           = 1140

Beispiel 2 — Alphabet aus Tabellengröße

Eine ausgelieferte Übergangstabelle hat 8192 Einträge bei |Q| = 64:

Rechnung Alphabet rückwärts

Alphabet = 8192 / 64
         = 128

Beispiel 3 — UTF-8-Bytestrom

DFA mit |Q| = 9 Zuständen über das volle Byte-Alphabet (|Σ| = 256):

Rechnung UTF-8

Übergaenge = 9 · 256
           = 2304