Minimierung von det. Aut. (I)

Id: min.tex,v 1.2 2004/12/14 12:36:40 waldmann Exp

Idee: Zustände zusammenlegen, die ,,das gleiche`` tun.

Das ,,gleich`` muß man aber passend definieren:

benutze Folge von Äquivalenz-Relationen $\sim_{0}^{}$ , $\sim_{1}^{}$ ,... auf Q

p $\sim_{k}^{}$ q$\iff$ Zustände p und q verhalten sich für alle Eingaben der Länge $\le$k beobachtbar gleich:

$$\forall$$w $$\in$$ $$\Sigma^{\le k}_{}$$ : w $$\in$$ L(A, p) $$\leftrightarrow$$ w $$\in$$ L(A, q).

äquivalent ist induktive Definition:

• (p $\sim_{0}^{}$ q) : $\iff$(p $\in$ F $\leftrightarrow$ q $\in$ F)
• (p $\sim_{k+1}^{}$ q) : $\iff$(p $\sim_{k}^{}$ q) $\wedge$ $\forall$c $\in$ $\Sigma$ : T(p, c) $\sim_{k}^{}$ T(q, c).