Minimierung von det. Aut. (II)

Nach Definition ist jeder Relation eine Verfeinerung der Vorgänger: $\sim_{0}^{}$ $\supseteq$ $\sim_{1}^{}$ $\supseteq$.... Da die Trägermenge Q endlich ist, kann man nur endlich oft verfeinern, und es gibt ein k mit $\sim_{k}^{}$ = $\sim_{{k+1}}^{}$ =.... Wir setzen $\sim$ : = $\sim_{k}^{}$.

Konstruiere A' = (Q', S', F', T') mit

• Q' = Q/ $\sim$ (Äquivalenzklassen)
• S' = [s]_$\sim$ (die Äq.-Klasse des Startzustands)
• F' = {[f]_$\sim$ | f $\in$ F} (Äq.-Kl. v. akzt. Zust.)
• für alle (p, c, q) $\in$ T : ([p]_$\sim$, c,[q]_$\sim$) $\in$ T'.

Satz: Wenn A vollständig und deterministisch,
dann ist A' ein kleinster vollst. det. Aut mit L(A') = L(A).