(1) Во-первых, покажите, что любой язык, который может быть принят конечным автоматом, также может быть принят детерминированным c автоматом нажатия. Напомним, что любой язык, принятый конечным автоматом, принимается детерминированным c конечным автоматом, а детерминированный c автомат с понижением может имитировать детерминированный c конечный автомат, просто не делая ничего интересного со своим стеком. Затем покажите, что DPDA принимает нерегулярный язык. 0 ^ n 1 ^ n хороший кандидат. Докажите, что этот язык является нерегулярным, используя лемму прокачки или теорему Майхилла-Нерода, затем покажите DPDA, который нажимает на 0 с, а затем переключается на выталкивание на 1 с.
(2) Во-первых, обратите внимание, что NPDA могут принимать любые язык, принятый DPDA, поскольку все DPDA также являются NPDA, которые не используют недетерминизм. Затем найдите язык, у которого есть NPDA, но нет DPDA. Палиндромы четной длины над алфавитом {0, 1} могут работать. Для этого есть простой NPDA, который недетерминированно угадывает, когда первая половина ввода была прочитана, и переключается с нажатия на нажатие. Чтобы показать, что нет DPDA, является более сложной задачей. Возможно, вы могли бы утверждать следующее: предположим, что был DPDA. Тогда в любой конфигурации DPDA возможен только один переход. Если строка w приводит к состоянию принятия в DPDA и очищает стек, x00 может привести к состоянию принятия или неприятия (поскольку x00 может быть или не быть палиндромом четной длины). Однако это противоречие, поэтому наша DPDA не существует. Кстати, тот же аргумент не работает для NPDA, потому что может быть несколько путей, поэтому один неудачный выбор ничего не значит.