Minimierung von det. Aut. (I)

Id: min.tex,v 1.1 2007-10-31 17:50:50 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 2008-01-24