Definition 7.2.3: a move of an LBA A = (S, _______, s0, R)is denoted by a pair of instantaneous descriptions; for IDs I1 and I2 we say I1 leads to I2 in A, I1 _— I2, if I1 = _1_2 … _k-1s_k … _n (1ŠkŠn) and either
(a)
(b) k>1,
Definition 7.2.4: a run of an LBA is just a sequence of (zero or more) moves of the machine; that is, there is a run from ID I1 to ID I2, I1 _—* I2 , provided there is asequence of IDs J0, J1, … , Jk (kŤ0) so that I1 = J0, I2 = Jk, and Ji _— Ji+1 for 0Ši
Definition 7.2.5: for an LBA the language recognized by A is L(A) = {w__*| s0w _—* _s for some s_R and ___*}.Language L is an LBA language if an LBA exists thataccepts it.
Previous slide | Next slide | Back to first slide | View graphic version |