Definition 3.2.1: Let M and N be DGSMs with _M = _N = _.For integer k>0, state s__SM is k-equivalent to state t__SN if _M(s, x) = _N(t, x) for all x___* with len(x) Š k.We write s _k t. States s and t are equivalent, written s _ t, provided that s _k t for all k>0. A DGSM is called distinguished provided it has no two distinct states that are equivalent.
Equivalence and k-equivalence are clearly equivalence relations and hence partition the state sets into equivalence classes. We denote the collection of equivalence classes of _ and _k by the notations_ and _k, respectively; for equivalence classes we write [s] = {t | s _ t } and [s]k = {t | s _k t }.
Previous slide | Next slide | Back to first slide | View graphic version |