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