The family of context sensitive languages is _____ under union and ____ under…

Answer: closed under union and closed under reversal.

Reason / Proof sketches:

• Union: If two languages are context-sensitive, each is accepted by a nondeterministic linear-bounded automaton (LBA). Construct a new nondeterministic LBA that on input nondeterministically chooses which of the two LBAs to simulate and then simulates it. Both simulations respect the same linear space bound, so the new machine is an LBA that accepts the union.

• Reversal: Given an LBA for a language L, build an LBA for the reversed language by first reversing the input in place on the bounded tape (use two pointers at the ends and swap symbols until the tape is reversed). This in-place reversal uses only the available linear tape and no extra unbounded storage. After reversing, simulate the original LBA on the reversed input. Thus the reversed language is also accepted by an LBA.