Lemma 3.2.1: Let M = (S, _, _, _, _, s0) be a DGSM and s,t__S. Then for each k>0
(a) s _k+1 t if and only if s _1 t and _(s, _) _k _(t, _) for all ____,
(b) _k+1 = _k implies _n = _k for all n > k, and
(c) _k+1 = _k implies s _ t if and only if s _k t.
Theorem 3.2.2: Let DGSM M = (S, _, _, _, _, s0) have N2 states. Then for s,t__S, s _ t if and only if s _N-1 t.
| Previous slide | Next slide | Back to first slide | View graphic version |