Могут ли автоматы с выпадающим меню иметь нулевые конечные состояния?
В соответствии с вопросом, могут ли автоматы с выпадением иметь нулевые конечные состояния?
3 ответа
Ага! Существует много разных определений КПК, но обычно это определение говорит о том, что КПК имеет набор принимающих состояний, который должен быть подмножеством набора всех состояний в КПК. Пустой набор является допустимым набором, поэтому КПК не обязательно когда-либо принимать. Вот как, например, можно построить КПК для пустого языка, который, как известно, не зависит от контекста.
Надеюсь это поможет!
Да, КПК может иметь нулевые конечные состояния. КПК, которым разрешено иметь более одного начального состояния (назовем их PDAI), вычислительно эквивалентны обычным КПК:
Проще говоря, каждый обычный PDA можно рассматривать как PDAI, который имеет одно начальное состояние. Каждый PDAI можно преобразовать в эквивалентный КПК с помощью описанного вами процесса. Так что да, PDAI принимают именно контекстно-свободные языки.
Некоторые формы автоматов нажатия принимаются путем остановки с пустым стеком в конце ввода. Для этой формы не существует такой вещи, как конечное состояние.