Пусть мы работаем в алфавите для входной записи , а для самой машины мы можем также использовать нули и единицы. Известно, что для хранения в памяти числа N в двоичном формате требуется битов. Так давайте будем в доп. памяти хранить число уже встреченных открывающихся скобок. Такое хранение потребует от нас логарифмической памяти. Если мы встретили закрывающуюся скобку, то уменьшаем на 1 число уже встреченных открывающихся скобок. Если встретили закрывающуюся и у нас записан ноль, то слово не принадлежит языку. Также нам потребуется некий функционал для определения границ на ленте, но это будет константная память для ограничивающих маркеров и на пространственную асимптотическую сложность не повлияет.