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