1. Compute _1 — this is accomplished by “inspection” of the output function for single letter input.
2. Repeat for k = 1, 2, 3, … until no classes split or k = N-1 Given _k, compute _k+1 as follows: for each pair of states s and t with s _k t, if _(s,_) _k _(t,_) for all ____, then s _k+1 t; otherwise split [s]k into [s]k+1 and [t]k+1.
3. At termination _k = _.
DGSM state equivalence algorithm
| Previous slide | Next slide | Back to first slide | View graphic version |