Coder Wiki | HowTos | Schnittmenge mehrerer Automaten

Dieses Kochrezept beschreibt das Vorgehen um die Schnittmenge von 2 DEAs zu erstellen.

Die beiden DEAs sehen wie folgt aus:

Links könnte man das kartesische Produkt der beiden Mengen bilden (dann müsste man im Nachhinein wieder kürzen) - ich habe mich entschieden Schritt für Schritt vorzugehen.

Unser erster Zustand ist das Produkt der beiden Startzustände: Also Z₀, S₀.

Mit Eingabe 0 geht es aus beiden Zuständen nicht weiter. Mit Eingabe 1 geht es von S₀ in S₁ und von Z₀ in Z₁.

δ	0	1
Z₀, S₀	-	Z₁, S₁
Z₁, S₁	-

Nach dem selben Verfahren erschließen sich uns auch die anderen Zustände.

δ	0	1
Z₀, S₀	-	Z₁, S₁
Z₁, S₁	-	Z₂, S₁
Z₂, S₁	Z₂, S₀	Z₂, S₁
Z₂, S₀	Z₂, S₀	Z₂, S₁

Die Schnittmenge der beiden Automaten sieht dann fertig so aus:

Coder How To's

Schnittmenge mehrerer Automaten