Definition 7.2.1: a linear bounded automaton (LBA) A is a 6-tuple A = (S, _______, s0, R), where S (states) is a finite non empty set, _ (tape alphabet) is a finite non empty set, ______(input alphabet) is a non empty set, s0_S (start state), R _ S (recognizing or accepting states), and _: S_____p(S___{l, r}) is the next-move function.
Definition 7.2.2: an instantaneous description (ID) for an LBA A = (S, _______, s0, R ) is a sequence _1s_2 where s_S and _1_2__*.
| Previous slide | Next slide | Back to first slide | View graphic version |