Hallo,
ich möchte zur Klausurvorbereitung aus diesem NEA/e einen vollständigen DEA mit minimaler Anzahl von Zuständen konstruieren.
Das Vorgehen habe ich grundsätzlich verstanden, es kommt mir aber zu umständlich und aufwendig vor.
Schritt 1: NEA/E -> NEA Elimination der Epsilon Übergänge
Übergangstabelle (in ε* schreibe ich wohin man mit dem ε gelangen kann, entweder nirgendwo, dann bleibt der Startzustand, sonst in Startzustand und den neuen Zustand):
δ
| 0
| 1
| ε
| ε*
|
->z0
| z2
| z1
| z3
| {z0,z3}
|
z1
| {z3,z1}
| ∅
| ∅
| {z1}
|
z2
| {z3,z2}
| ∅
| ∅
| {z2}
|
z3*
| ∅
| ∅
| ∅
| {z3}
|
bei der Transformationstabelle lasse ich nun das ε weg und schaue, in welchen Zustand ich jeweils gelange, wenn ich 0 oder 1 eingebe. Dabei muss ich nun für z0 berücksichtigen, dass auch z3 in der Potenzmenge ist , also muss ich für z0 gucken wo ich mit einer 0 von z0 und mit einer 0 von z3 hinkomme.
δ
| 0
| 1
|
->z0
| z2
| z1
|
z1
| {z3, z1}
| ∅
|
z2
| {z3,z2}
| ∅
|
z3*
| ∅
| ∅
|
Der Automat sieht dann genauso auf wie oben auf dem Bild, nur ohne den Epsilon Übergang (z4 habe ich einfach weggelassen, weil er nicht erreichbar ist).
Nun muss ich eine Potenzmengenkonstruktion für die Umformung des NEA in einen DEA vornehmen, ich fange mit dem Startzustand an, übernehme ihn aus der alten Tabelle und für jedes neue z, lege ich einen neuen Zustand an für den ich wieder betrachte, was nach der Eingabe von 0 und 1 geschieht.
δ
| 0
| 1
|
->z0
| z2
| z1
|
z1
| {z3,z1}*
| ∅
|
z2
| {z3,z2}*
| ∅
|
{z3,z1}*
| {z3, z1}*
| ∅
|
{z3,z2}*
| {z3,z2}*
| ∅
|
Wann kann ich sagen, dass 2 Zustände äquivalent sind?
Meiner Meinung nach sind z1 und z2 äquivalent, weil sie nur zu z3 oder sich selbst führen. Dasselbe gibt aber auch für {z3,z1} und {z3,z2}. Also sind die unteren 4 Zustände äquivalent?
Wie würde nun das Diagramm zum DEA aussehen?
->z0-----0,1---->z1z2-----0---->z3z2z1
Ich möchte hauptsächlich verstehen, wann ich welche Zustände weglassen kann und warum.
