Wir gehen von einer existierenden Überführungsfunktion aus.
easy-coding.de/Attachment/859/…f84a95c97fbe7422ac1edf10a
Nun erstellen wir ein neue leere Tabelle mit der Überführungsfunktion δ'
Links entstehen die neuen Zustände des DEAs. Diese nummerieren wir durch.
Wir betrachten S0. Mit der Eingabe 0 führt er in die Zustände S0, S1.
Diese Zustände betrachten wir nun als ein einziges Zustandstupel.
Wir nennen es (1).
easy-coding.de/Attachment/860/…f84a95c97fbe7422ac1edf10a
Mit der Eingabe 1 führt S0 in sich selbst (den Zustand S0) - da dieser Zustand schon existiert brauchen wir ihn der Liste nicht hinzufügen.
Wir betrachten den nächsten Zustand in unserer Liste auf der linken Seite. Es ist das Zustandstupel {S0, S1} - als Eingabe nehmen wir wieder zuerst die 0. Jetzt betrachten wir alle Zustände im Tupel. S0 führt zu S0, S1 und S1 führt zu S2. Es entsteht also das Tupel aus S0, S1, S2, S2 (doppelte Zustände existieren in einem Tupel nicht).
Wohin kommen wir von {S0, S1} mit der Eingabe 1?
Von S0 gelangen wir auf S0 und von S1 gelangen wir auf S2. Das entstehende Tupel lautet also {S0, S2}. Da es noch nicht in unserer Liste links ist, fügen wir es hinzu.
easy-coding.de/Attachment/861/…f84a95c97fbe7422ac1edf10a
Wenn wir dies fortführen entsteht eine komplette Überführungsfunktion, mit Hilfe derer wir den neuen Automaten (einen DEA) zeichnen können.
easy-coding.de/Attachment/862/…f84a95c97fbe7422ac1edf10a
easy-coding.de/Attachment/859/…f84a95c97fbe7422ac1edf10a
Nun erstellen wir ein neue leere Tabelle mit der Überführungsfunktion δ'
Links entstehen die neuen Zustände des DEAs. Diese nummerieren wir durch.
Wir betrachten S0. Mit der Eingabe 0 führt er in die Zustände S0, S1.
Diese Zustände betrachten wir nun als ein einziges Zustandstupel.
Wir nennen es (1).
easy-coding.de/Attachment/860/…f84a95c97fbe7422ac1edf10a
Mit der Eingabe 1 führt S0 in sich selbst (den Zustand S0) - da dieser Zustand schon existiert brauchen wir ihn der Liste nicht hinzufügen.
Wir betrachten den nächsten Zustand in unserer Liste auf der linken Seite. Es ist das Zustandstupel {S0, S1} - als Eingabe nehmen wir wieder zuerst die 0. Jetzt betrachten wir alle Zustände im Tupel. S0 führt zu S0, S1 und S1 führt zu S2. Es entsteht also das Tupel aus S0, S1, S2, S2 (doppelte Zustände existieren in einem Tupel nicht).
Wohin kommen wir von {S0, S1} mit der Eingabe 1?
Von S0 gelangen wir auf S0 und von S1 gelangen wir auf S2. Das entstehende Tupel lautet also {S0, S2}. Da es noch nicht in unserer Liste links ist, fügen wir es hinzu.
easy-coding.de/Attachment/861/…f84a95c97fbe7422ac1edf10a
Wenn wir dies fortführen entsteht eine komplette Überführungsfunktion, mit Hilfe derer wir den neuen Automaten (einen DEA) zeichnen können.
easy-coding.de/Attachment/862/…f84a95c97fbe7422ac1edf10a
15.760 mal gelesen