Informatik zum Jahresanfang – noch eine Variation

[Gunnar Bittersmann]

@@Matthias Apsel

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.

Ja, die wären auch jeweils paarweise zu prüfen.

Und wo ich das schon in einer DM erläutert hatte, stelle ich’s auch hier rein.

Schauen wir uns diesen 2er Automaten an:

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.

Beides sind keine Endzustände, deshalb kann man S₁ und S₂ zusammenfassen:

Das o.g. Kriterium allein reicht aber nicht.

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S₁ und mit 0, 2, 4, 6, 8 zu E.

Trotzdem kann man auch diesen Automaten genauso reduzieren.

Da müsste ich nochmal drüber nachdenken oder nachlesen (vielleicht hab ich sogar noch meine Unterlagen aus Theoretischer Informatik von der Uni irgendwo im Schrank), wie man das auch noch mit reinbekommt.

Schauen wir uns nochmal den 3er Automaten an:

Von s₀ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.
Von sₑ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.

Stimmt auch überein. Wenn man nun s₀ und sₑ zusammenfassen würde:

Das hatten wir doch schon! 😉

s₀ und sₑ darf man nicht zusammenfassen, da der eine ein Endzustand ist, der andere aber nicht.

LLAP 🖖