The number of possible sequences of register operations along an -loop is unbounded, but it is easy to prove that there are only finitely many equivalence classes of such sequences: Two sequences are in the same equivalence class if and only if they have the same effect on the state of the machine; since each machine has a finite number of configurations (see theorem 1), there are only finitely many such equivalence classes.
the basic idea behind the construction is as follows: If there exists an -path from q 1 to q 2 with the register operations a over its arcs, and an arc (q 2 , σ, b , q 3 ) Figure 9 removal paradigm.