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/…d0d18a318d47b024cf0a36f66
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/…d0d18a318d47b024cf0a36f66
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…d0d18a318d47b024cf0a36f66
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/…d0d18a318d47b024cf0a36f66
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/…d0d18a318d47b024cf0a36f66
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…d0d18a318d47b024cf0a36f66
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.
18.784 mal gelesen