Automaten-Synthese (II)

Konstruktion induktiv über den Aufbau von X:

• für c $\in$ $\Sigma$ $\cup$ {$\epsilon$}: p₀$\;\stackrel{{c}}{{\to}}\;$p₁
• für s_X$\;\stackrel{{X}}{{\to}}\;$f_X, s_Y$\;\stackrel{{Y}}{{\to}}\;$f_Ye :
  • s$\;\stackrel{{X \cdot Y}}{{\to}}\;$f durch s = s_X, f_X = s_Y, f_Y = f.
  • s$\;\stackrel{{X + Y}}{{\to}}\;$f durch s$\;\stackrel{{\epsilon}}{{\to}}\;$s_X, s$\;\stackrel{{\epsilon}}{{\to}}\;$s_Y, f_X$\;\stackrel{{\epsilon}}{{\to}}\;$f, f_Y$\;\stackrel{{\epsilon}}{{\to}}\;$f
  • s$\;\stackrel{{X^*}}{{\to}}\;$f durch s$\;\stackrel{{\epsilon}}{{\to}}\;$s_X, s$\;\stackrel{{\epsilon}}{{\to}}\;$f, f_X$\;\stackrel{{\epsilon}}{{\to}}\;$s_X, f_X$\;\stackrel{{\epsilon}}{{\to}}\;$f.

Satz. Der so erzeugt Automat A ist korrekt. | Q(A)|$\le$2| X|.

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

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