Для такого языка, как 0 ^ n 1 ^ n, мы нажимаем символ конца стека, затем нажимаем 0 каждый раз, когда 0 читается из ввода. На первой 1 мы начинаем выталкивать 0 из стека.
Исправьте пока.
В идеальном мире, как только мы доберемся до конца входной строки, единственное, что в стеке будет символом конца стека, и мы сможем выполнить этот последний переход.
Это не обязательно тот случай, когда в этом случае вообще должны быть переходы. Это в определенной степени зависит от того, как вы определяете КПК и как вы хотели бы, чтобы ваш КПК работал. КПК обычно могут принимать, принимая состояние, пустой стек или как пустое состояние, так и пустой стек вместе. Я предпочитаю последний из них, поскольку он оставляет меньше всего воображению. Однако все они являются полностью эквивалентными определениями с точки зрения вычислительной мощности.
Что произойдет, если на входе еще 1 с. Например, строка ввода 00111.
Хороший вопрос. Если у вас есть 1 на входе после очистки стека, строка не на том языке, который вы пытаетесь принять. На этом этапе вам нужно решить, как вы хотите отклонить этот ввод. Один из распространенных методов - просто оставить неопределенным переход, который необходимо выполнить в таких случаях. Когда это происходит и ввод остается, машина, как говорят, "сбой" и, по умолчанию, она не может принять ввод. Другой вариант, как вы могли бы предположить, - добавить новое «мертвое» состояние, чтобы явно кодировать операцию исчерпания любого оставшегося ввода.
Если вам необходимо иметь явные мертвые состояния и как вы хотите указать, что ваш КПК принимает подтверждение, это в основном соглашения, которые вы можете выбрать (или которые указаны для вас вашим инструктором).