Definition 3.4.1: a non deterministic n-tape acceptor (n-NFA) A is a (n+5)-tuple, A = (S, _, _, s0, S1, … , Sm, R) where S is a finite non-empty set (the states), _ is a finite non-empty set (the alphabet), s0__S, Si,R _ S (states that read from tape i (1ŠiŠn), and final or recognition states, respectively), _: S__(____{_}) _ p(S) (the next-state function); the subsets Si are required to partition the state set S, that is, S = S1 _ S2 _ … _ Sm, and Si _ Sj = _ if i°j.
If for every state s and letter _, _(s,_) has exactly one element and _(s,_) is empty, then A is deterministic (n-DFA).
| Previous slide | Next slide | Back to first slide | View graphic version |