Участник:Rodinasophie/ex-braces-parse-in-logspace — Решение Родина — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
 
Строка 4: Строка 4:
 
Пусть мы работаем в алфавите для входной записи <m>{(,)}^*</m>, а для самой машины мы можем также использовать нули и единицы. Известно, что для хранения в памяти числа N в двоичном формате требуется <m>\log N</m> битов. Так давайте будем в доп. памяти хранить число уже встреченных открывающихся скобок. Такое хранение потребует от нас логарифмической памяти. Если мы встретили закрывающуюся скобку, то уменьшаем на 1 число уже встреченных открывающихся скобок. Если встретили закрывающуюся и у нас записан ноль, то слово не принадлежит языку. Также нам потребуется некий функционал для определения границ на ленте, но это будет константная память для ограничивающих маркеров и на пространственную асимптотическую сложность не повлияет.
 
Пусть мы работаем в алфавите для входной записи <m>{(,)}^*</m>, а для самой машины мы можем также использовать нули и единицы. Известно, что для хранения в памяти числа N в двоичном формате требуется <m>\log N</m> битов. Так давайте будем в доп. памяти хранить число уже встреченных открывающихся скобок. Такое хранение потребует от нас логарифмической памяти. Если мы встретили закрывающуюся скобку, то уменьшаем на 1 число уже встреченных открывающихся скобок. Если встретили закрывающуюся и у нас записан ноль, то слово не принадлежит языку. Также нам потребуется некий функционал для определения границ на ленте, но это будет константная память для ограничивающих маркеров и на пространственную асимптотическую сложность не повлияет.
  
[[Категория:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]

Текущая версия на 15:49, 20 мая 2020


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