Partitionierungsverfahren

$$ L(A) = \{ w \in \Sigma^* \mid w \text{ enthält } 00 \} $$
A = (Q, Σ, δ, q₀, F) Q = { q0, q1, q2, q3, q4 } Σ = { 0, 1 } q₀ = q0 F = { q4 }
δ(q, σ)01
q0q1q2
q1q4q2
q2q3q2
q3q4q0
q4q4q4

Schritte

1. Partitionen erstellen

Teile die Zustände in zwei Partitionen auf: eine Partition mit allen Endzustände, die andere mit allen Nicht-Endzuständen

Partitionen: { }

2. Partitionen verfeinern

Prüfe für jede Partition: Führen die gleichen Symbole zu Zuständen in derselben Partition?

Falls Zustände unterschiedliche Folgepartitionen ansteuern, wird die Partition aufgeteilt.

Wiederholen bis sich keine weiteren Änderungen mehr ergeben

{ }

Testen mit Symbol: 0

Neue Partitionen: { { q4 } , { q0, q2 } , { q1, q3 } }

3. Zustände zusammenfassen

Jede Partition wird zu einem neuen Zustand zusammengefasst. Alle Partitionen die einen Startzustand haben, werden zu einem Startzustand. Alle Endzustände werden zu Endzuständen.

4. Übergänge konstruieren

Da alle Zustände einer Partition äquivalent sind, reicht ein beliebiger repräsentativer Zustand aus, um die Ziel-Partition zu bestimmen.

Quellen

https://martin-thoma.com/minimierung-eines-automaten-mittels-aquivalenzklassenkonstruktion
https://www.tcs.ifi.lmu.de/lehre/ss-2023/fsk_de/14-dfa-minimierung.pdf
https://www.informatik.uni-bremen.de/agbs/lehre/ss05/pi2/hintergrund/minimize_dfa.pdf