By taking _ = _ __(____ {A, B, C, …}) positions on an LBA tape can be “marked” without obliterating the input,
a b c …
can become
a b c …A …
See Example 7.2.3 in the text for a detailed illustration.
Previous slide | Next slide | Back to first slide | View graphic version |