Участник:Rodinasophie/ex-braces-parse-in-logspace — Решение Родина

Материал из DISCOPAL
< Участник:Rodinasophie
Версия от 15:49, 20 мая 2020; StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


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