Definition 1.2.6: A non-deterministic finite acceptor (NFA) A is a 5-tuple, A = (S, _, _, s0, R), where (S, _ , _) is a non-deterministic transition system, s0__S is the start state, and R _ S is the set of recognizing (or accepting) states.
The language recognized (or accepted) by A is L(A) = {x_ _* | _(s0, x)__R°_}. A language L _ _* is NFA-recognizable if there exists a NFA A so that L = L(A).
For an NFA A as in Definition 1.2.6 and x____*, say x=_1_2 … _k (kŤ0) with _i______(1ŠiŠk), we say x has a run s0, s1, … , sk in A if s1_ _(s0, _1), s2_ _(s1, _2), ... , sk_ _(sk-1, _k). A run is recognizing (or accepting) if sk__R.
| Previous slide | Next slide | Back to first slide | View graphic version |