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/…27514cba9b8d66c481a9cd17b
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/…27514cba9b8d66c481a9cd17b
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…27514cba9b8d66c481a9cd17b
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/…27514cba9b8d66c481a9cd17b
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/…27514cba9b8d66c481a9cd17b
3. Übergangsfolgen bereinigen
easy-coding.de/Attachment/858/…27514cba9b8d66c481a9cd17b
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.