Ein ε-NEA ist ein nicht-deterministischer endlicher Automat mit ε-Übergängen.
Ein NEA ist ein Nicht-deterministischer endlicher Automat.
1. Zyklus eliminieren
Falls ε-Zyklen existieren, fasse alle Zustände eines Zyklus zu einem zusammen und übernehme alle von ε verschiedenen Eingabezeichen des Zyklus in einer Schleife
easy-coding.de/Attachment/856/…3a2cdce7ff3241ac884e08cd6
2. Zustände zu Endzuständen
Mache jeden Zustand s, von dem aus eine ε-Übergangssequenz in einen Endzustand führt, selbst zu einem Endzustand.
easy-coding.de/Attachment/857/…3a2cdce7ff3241ac884e08cd6
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…3a2cdce7ff3241ac884e08cd6
4. Alle restlichen Übergänge, die von s mit a 6=e nach t übergehen bleiben unverändert.
5. Entferne alle im neuen Diagramm nicht mehr erreichbaren Zustände.
Falls ε-Zyklen existieren, fasse alle Zustände eines Zyklus zu einem zusammen und übernehme alle von ε verschiedenen Eingabezeichen des Zyklus in einer Schleife
easy-coding.de/Attachment/856/…3a2cdce7ff3241ac884e08cd6
2. Zustände zu Endzuständen
Mache jeden Zustand s, von dem aus eine ε-Übergangssequenz in einen Endzustand führt, selbst zu einem Endzustand.
easy-coding.de/Attachment/857/…3a2cdce7ff3241ac884e08cd6
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…3a2cdce7ff3241ac884e08cd6
4. Alle restlichen Übergänge, die von s mit a 6=e nach t übergehen bleiben unverändert.
5. Entferne alle im neuen Diagramm nicht mehr erreichbaren Zustände.
19.050 mal gelesen