Как создать машину Тьюринга, которая может распознавать строки сбалансированных скобок? Например (())().
Машина Тьюринга для сбалансированных скобок
comment
Пройдите обзор, чтобы узнать, как работает Stack Overflow, и прочитайте Как спросить о том, как улучшить качество вашего вопроса. Также посетите справочный центр, чтобы узнать, какие вопросы вы можете задать.
- person Progman schedule 26.01.2020
comment
Вам даже не нужна машина Тьюринга; выталкивающего автомата было бы достаточно.
- person chepner schedule 26.01.2020
Ответы (1)
Чтобы распознать строки со сбалансированными скобками, нам просто нужно убедиться, что нет префикса, в котором больше закрывающих скобок, чем открывающих скобок, и что строка заканчивается после просмотра равного количества открывающих и закрывающих скобок. Ясно, что оба эти условия должны выполняться для допустимых строк; это необходимые требования. Я оставлю доказательство достаточности этих условий в качестве упражнения или, во всяком случае, предлагаю вам задать отдельный вопрос по этому поводу.
Итак, все, что нам нужно сделать, это следующее:
- читать ввод слева направо
- на вспомогательной ленте (если она многоленточная) или справа от входа (если одноленточная), отслеживайте текущую разницу (#open - #closed), видимую до сих пор
- остановить-отклонить, если разница когда-либо опустится ниже нуля
- halt-reject, если вы дошли до конца ввода и разница не равна нулю
- halt-accept, если вы дошли до конца ввода и разница равна нулю
Предполагая одноленточный TM, вы можете прочитать символ, затем написать поверх него каким-либо маркером, затем перейти к концу ленты в состоянии, зависящем от того, увидели ли вы открывающую или закрывающую скобку; затем либо добавьте новый символ в конец (при открытии), либо удалите один с конца (при закрытии); затем войдите в новое состояние, чтобы вернуться к первому немаркированному символу ввода, и повторите.
person
Patrick87
schedule
27.01.2020
