Minimierung von det. Aut. (I)

Id: min.tex,v 1.3 2005/10/26 21:31:59 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:

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

äquivalent ist induktive Definition:



Johannes Waldmann 2006-02-02