Zu jedem NEA existiert ein äquivalenter NEA mit maximal zwei Endzuständen

Question

Hallo zusammen,

ich sitze seit längerem an meiner letzten Aufgabe. Ich habe nicht mal einen Ansatz diese zu beweisen :/

Und zwar muss ich folgende Aussage beweisen: Zu jedem NEA existiert ein äquivalenter NEA mit
maximal zwei Endzuständen.

Ich bin für jede Hilfe sehr dankbar!

Grüße und schönen 4. Advent

Answer 1

1. Füge einen neuen Zustand \(q_\text{F}\) hinzu.

2. Für jeden Endzustand \(q\):

   1. Für jede Transition \(q'\stackrel{\sigma}{\to}q\), füge die Transition \(q'\stackrel{\sigma}{\to}q_\text{F}\) hinzu.
      

   2. Wenn \(q\) nicht der Startzustand ist, dann entferne \(q\) aus der Menge der Endzustände.

3. Füge \(q_\text{F}\) zur Menge der Endzustände hinzu.