0 Daumen
274 Aufrufe

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

Avatar von

1 Antwort

0 Daumen
  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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community