Definition 3.4.2: if A = (S, _, s0, _, S1, … , Sn, R) is an n-NFA, an instantaneous description (ID) for A is an (n+1)-tuple where s__S is the current state, and wi___* (1ŠiŠn) is the remaining content of the ith input tape.
Definition 3.4.3: IDs _= and _= of a n-NFA A = (S, _, s0, _, S1, … , Sn, R) determine a run-step, written _ |_ _, provided that t___(s,_), s__Si, wi = _ xi, and wj= xj for j°i; a run of length kŤ0 from ID _ to ID _, written _ |_* _, is a sequence of IDs, _0, … , _k (kŤ0) so that _=_0, _=_k, and _i |_ _i+1 for 0Ši
Definition 3.4.4: the relation recognized (or accepted) by n-NFA A = (S, _, s0, _, S1, … , Sn, R) is L(A) = { | wi___* (1ŠiŠn), |_* , and s__R}.