Automaten-Synthese (II)

Konstruktion induktiv über den Aufbau von X:

Satz. Korrektheit: L(A) = L(X). Größe: | Q(A)|$ \le$2| X|.


Aufgabe: Warum braucht man bei X* die zwei neuen Zustände s, f und kann nicht s = sX oder f = fX setzen?

Hinweise: (wenigstens) eine der Invarianten wird verletzt, und damit eine der anderen Konstuktionen inkorrekt.



Johannes Waldmann 2006-02-02