Nichtdeterministischen Automat beweisen

Question

Aufgabe:

Beschreiben Sie, wie man neue DEAs N1 und N2 konstruiert die
dieselben Zustände wie M besitzen und die erfüllen dass
a) L(N1) = {u : u ist Anfangssück eines w ∈ L(M)}.
b) L(N2) = {u : u hat ein Anfangsstück das in L(M) liegt}.

Problem/Ansatz:

Ich habe leider keinen Ansatz wie ich die Aufgabe lösen soll, für Hilfe bin ich dankbar.

Comments

Wie sieht der Automat M aus?

---

Ich habe die Frage nicht verstanden deswegen frage ich hier also die Aufgabenstellung sieht so aus.

Answer 1

zu a) Sei E die Menge der Zustände, von denen aus ein Endzustand erreicht werden kann. Füge E zur Menge der Endzustände hinzu.

zu b) Entferne alle Transitionen, die von einem Endzustand ausgehen. Füge dann für jeden Endzustand \(q\) und jeden Buchstaben \(a\in \Sigma\) die Transition

        \(q\stackrel{a}{\to}q\)

hinzu.