Чтобы распознать строки сбалансированных скобок, мы просто должны убедиться, что нет префикса, который имеет больше закрывающих скобок, чем открывающие скобки, и что строка заканчивается после просмотра одинакового количества открывающих и закрывающих скобок. Ясно, что оба эти условия должны выполняться для допустимых строк; это необходимые требования. Я оставлю указание на то, что эти условия являются достаточными в качестве упражнения, или, во всяком случае, предлагаю вам задать отдельный вопрос по этому вопросу.
Итак, все, что нам нужно сделать, это следующее:
- читать вход слева направо
- на вспомогательной ленте (если многоканальная) или справа от входа (если одиночная лента), отслеживать текущую разницу (#open - #closed), видимую до сих пор
- остановка-отклонение, если разница когда-либо опускается ниже нуля
- остановка-отклонение, если вы доходите до конца ввода, а разница не равна нулю
- остановка-принятие если вы дойдете до конца ввода, а разница равна нулю
Предполагая, что ТМ на одной ленте, вы можете прочитать символ, затем написать его с помощью некоторого маркера, а затем перейти к концу лента в состоянии в зависимости от того, видели ли вы открывающую или закрывающую скобку; затем либо добавьте новый символ в конец (при открытии), либо удалите один с конца (при закрытии); затем введите новое состояние для go назад к первому неотмеченному символу ввода и повторите.