Übung 3 - H1b (Potenzmengen-Trick / Tabelle)

doemel
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 23. Okt 2010 11:45
Kontaktdaten:

Übung 3 - H1b (Potenzmengen-Trick / Tabelle)

Beitrag von doemel »

Hallo zusammen.

Kann mir irgend jemand erklären was es mit dieser ominöse Tabelle auf sich hat? Ich versteh wie die sich aufbaut (laut Skript) aber seh in ihr keinen nennensswerten Sinn.
Den DFA hab ich hinbekommen aber der Sinn der Tabelle erschließt sich mir überhaupt nicht.

Danke sachonmal für sinnvolle Antworten

MfG Dömel

claudius
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 4. Okt 2010 16:20

Re: Übung 3 - H1b (Potenzmengen-Trick / Tabelle)

Beitrag von claudius »

Die Tabelle dient als Grundlage für den Automaten den du erzeugen sollst.
Das Vorgehen mit dem NFA im Skript ist in etwa so:
Du gehst zum Startzustand 0 und schaust was geschieht wenn du a, b oder c eingibst.
  • Bei a geht er nach 0 oder 1 → {0,1}
  • Bei b geht er nach 0 → {0}
  • Bei c geschieht nichts → ∅
Nun ist der Trick das du {0,1} als neuen Zustand für deinen DFA nimmst. Du schaust also was an den Stellen 0 und 1 geschieht wenn du a, b oder c eingibst.
  • Bei a gehst du in 0 nach 0 oder nach 1 und in 1 geschieht nichts → {0,1}.
  • Bei b gehst du in 0 nach 0 und in 1 nach 2 → {0,2}.
  • Bei c gehst geschieht in 0 nichts und in 1 gehst du nach 3 → {3}.
Nun machst du das gleiche Spiel mit dem neuen Zustand {0,2}
  • Bei a gehst du in 0 nach 0 oder 1 und in 2 geschieht nichts → {0,1}.
  • Bei b gehst du in 0 nach 0 und in 2 geschieht nichts → {0}.
  • Bei c geschieht in 0 nichts und in 2 auch nichts → ∅.
Da alle "Virtuellen" Zustände jetzt abgehandelt sind schaust du dir noch den Zustand 3 an
in 3 geschiet egal bei welcher Eingabe überhapt nichts → 3 x ∅

Zur Konvention zählt dann noch die Zeile mit den 4 ∅

Jetzt kannst du aus der Tabelle einen DFA bauen mit den vier Zuständen {0},{0,1},{0,2},{3} die "Virtuellen" Zustände werden als normale Zustände angesehen und du hast deinen DFA.

doemel
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 23. Okt 2010 11:45
Kontaktdaten:

Re: Übung 3 - H1b (Potenzmengen-Trick / Tabelle)

Beitrag von doemel »

Alles klar. Ich finde es zwar immer noch einfacher sich das grad im Kopf zu überlegen aber jetzt weiß ich auch was es mit dieser Tabelle auf sich hat.

Dankeschön.

MfG Dömel

Antworten

Zurück zu „Archiv“