Lemma 7.3.4: for each LBA A = (SA, _, _A, _A, sA, RA), there is an LBA B = (SB, _, _B, _B, sB, RB), so that when B is started on input x__+, it terminates its run with its tape containing a representation of the number of IDs _ of A so that sAx _—* _ in A.
Theorem 7.3.5: the context-sensitive languages are closed under complement.
Previous slide | Next slide | Back to first slide | View graphic version |