Altklausur WS 2009/10

[H_Arete]

---

@rwanka

@H Arete

@pzi

Und das geht wie folgt:

Anmerkung, kann es sein, dass diese Vereingungsmenge nur ausreicht, wenn q_1 der einzige Startzustand ist, also S = {q_1} ???
Streng genommen müssen alle i,j berücksicht werden, wobei q_j in F und q_i in S ???

Es gibt ja per Definition des DFA auch nur einen Startzustand.

Anderenfalls, also mit mehr als einen Startzustand, wüßte man ja nicht, wo man anfangen soll, und hätte somit einen nichtdeterministischen FA. Aber dann kann man einen neuen Zustand q’[sub]0[/sub] hinzunehmen, den mit ε-Übergängen an die (nun veraltenden) Startzustände anbinden und q’[sub]0[/sub] als einzigen Startzustand nehmen. Wenn man diesen NFA nun wieder in einen DFA verwandelt, kommt ein DFA mit genau einem Startzustand raus. Also braucht man nie (weder bei DFA noch NFA) mehrere Startzustände.

MfG

Rolf Wanka

D-ACK.

(Assoziation: Die Idee ein Super-Startzustand q_0 einzuführen erinnert mich an die mehrere-Senken-Problematik bei maximalen s-t-Flüßen… )