Notizen

Table-Filling-Algorithmus

tagstheoretische_informatik, formale_sprachtheorie

Der Table-Filling-Algorithmus ist ein Algorithmus, der aus einem beliebigen DEA einen Minimalautomat macht.

Wir gehen von folgendem Beispielautomaten aus, der nun minimiert werden soll:

Der Algorithmus geht nun wie folgt vor:

  1. Tabelle aller Zustandspaare aufstellen

Da die Zustandspaare und äquivalent sind, reicht es, nur eine Kombination hinzuschreiben. Auch das Zustandspaar kann vernachlässigt werden:

Misplaced & q_1 & . \\ q_2 & . & . \\ q_3 & . & . & . \\ q_4 & . & . & . & . \\ & q_0 & q_1 & q_2 & q_3 \end{matrix}$$ 2. **Alle Paare $(q, q')$ markieren bei denen ein Zustand ein Endzustand ist und der andere nicht** In unserem Fall ist nur $q_4$ ein Endzustand und alle anderen Zustände nicht, also werden alle Kombinationen wo $q_4$ dabei ist markiert: $$\begin{matrix} q_1 & . \\ q_2 & . & . \\ q_3 & . & . & . \\ q_4 & X & X & X & X \\ & q_0 & q_1 & q_2 & q_3 \end{matrix}$$ 3. **Für alle unmarkierten Paare $(q, q')$ und jeden Buchstaben $a \in \Sigma$: Testen, ob $(\delta(q,a),\delta(q',a))$ bereits markiert ist. Wenn ja, *Ausgangspaar* $(q, q')$ markieren** Dafür zur Hilfe erst alle Zustandspaare rausschreiben, die noch nicht markiert wurden (Farben können vorerst ignoriert werden): $$\begin{matrix} q_1 & . \\ q_2 & . & . \\ q_3 & \color{cyan}. & . & . \\ q_4 & X & \color{red}X & X & X \\ & q_0 & q_1 & q_2 & q_3 \end{matrix} \hspace{3cm} \begin{matrix} (1,0) \\ (2,0) & (2,1) \\ \color{orange}(3,0) & (3,1) & (3,2) \\ \ \\ \ \end{matrix}

Dann deren Übergänge bei jedem Buchstaben notieren:

ÜÜ

Jetzt für jedes Pärchen nach Übergang schauen, ob es in der Zustandspaartabelle bereits markiert ist. Wenn ja, dann das Ausgangspärchen markieren.

Beispiel: Das Pärchen wird bei lesen von 0 zu , dieses ist markiert () daher muss das Ausgangspärchen in der Tabelle markiert werden ().

  1. Schritt 3 solange wiederholen, bis Tabelle invariant

Wenn man das so oft wiederholt bis keine neuen Markierungen dazu kommen, erhält man folgende Tabelle:

Misplaced & q_1 & X \\ q_2 & . & X \\ q_3 & X & . & X \\ q_4 & X & X & X & X \\ & q_0 & q_1 & q_2 & q_3 \end{matrix}$$ 5. **Alle nicht-markierten Paare zu je einem Zustand verschmelzen** Die nicht markierten Paare sind in unserem Fall $(q_2, q_0)$ und $(q_3, q_1)$ und können zu den Zuständen $q_{02}$ und $q_{13}$ verschmolzen werden. Dann werden alle verschmolzenen und übrigen Zustände hingeschrieben und sollten von den Übergängen aufgehen: ![[automatenminimierung_nacher.jpg]]

Backlinks