1) У DPDA есть один стек, поэтому DPDA с двумя стеками может определенно делать все, что может делать DPDA, просто не используя (или тривиально используя) второй стек.2) DPDA с двумя стеками может распознавать язык слов с одинаковыми номерами a, b и c, используя первый стек, чтобы гарантировать, что число a равно числу b, и второй стек, чтобы гарантировать количествоb равно количеству c.Поскольку этот язык не является контекстно-свободным, для него не существует DPDA с одним стеком;следовательно, DPDA с 2 стеками не равен.Поскольку мы знаем, что DPDA является подмножеством или равно DPDA с двумя стеками, то мы знаем, что DPDA с двумя стеками не является подмножеством или равно DPDA.3) это трудно сказать, попытка будет предпринята позже 4) определенно нет, по тому же аргументу, что и для (2).
Что касается (3) - я сильно подозреваю, что DPDA с 2 стеками может имитироватьдетерминистическая TM, которая подразумевает NPDA, является подмножеством 2-стекового DPDA.Чтобы доказать это, нужно показать, как моделировать работу любой TM с использованием DPDA с 2 стеками.Я думаю, что-то вроде этой визуализации может быть достаточно ...
_ _ _ _ _ _ _ _ _ _ _ _ _ _
|Z|_|_|_|_|_|_| |_|_|_|_|_|_|Z|
stack #1 ^ stack #2
TM
Вход первоначально записан полностью в стеке # 2.Чтобы двигаться вправо, TM выскакивает из стека # 2 и толкает в стек # 1.Чтобы двигаться влево, TM выскакивает из стека # 1 и толкает в стек # 2.Текущая ячейка ленты всегда является вершиной стека # 2.DPDA с 2 стеками может делать все, что может делать детерминированный TM с точки зрения состояний и переходов;и он может использовать два стека для имитации ленты, как указано выше.Например, TM, принимающий недетерминированный контекстно-свободный язык всех палиндромов, работает следующим образом:
- проверьте первую ячейку.если пусто, остановите прием.В противном случае напишите пробел и перейдите в состояние End (s), где s - наблюдаемый символ.
- в состоянии End (s) двигайтесь вправо, пока не найдете пробел.Затем переместитесь влево и войдите в состояние Check (s).
- , находясь в состоянии Check (s), подтвердите наблюдаемый символ s.Если нет, то остановите-примите, если пусто, и остановите-отклоните в противном случае.В противном случае напишите пробел, введите состояние IsFinished и переместитесь влево.
- , находясь в состоянии IsFinished, проверьте, не заполнена ли ячейка ленты.Если так, остановитесь, примите.В противном случае введите состояние «Старт» и двигайтесь влево.
- , находясь в состоянии «Старт», двигайтесь влево, пока не найдете пробел.Затем переместитесь вправо и снова войдите в начальное состояние.
Пример на ТМ против DPDA с 2 стеками:
DTM 2-stack DPDA
------- --------------------
tape State Stack #1 Stack #2
B11011B Z 11011Z
^ initial ^
BB1011B ZB 1011Z
^ End(1) ^
BB1011B ZB1 011Z
^ End(1) ^
BB1011B ZB10 11Z
^ End(1) ^
BB1011B ZB101 1Z
^ End(1)
BB1011B ZB1011 Z
^ End(1) ^
BB1011B ZB101 1Z
^ Check(1) ^
BB101BB ZB10 1BZ
^ IsFin ^
BB101BB ZB1 01BZ
^ Start ^
BB101BB ZB 101BZ
^ Start ^
BB101BB Z B101BZ
^ Start ^
BB101BB ZB 101BZ
^ Initial ^
BBB01BB ZBB 01BZ
^ End(1) ^
BBB01BB ZBB0 1BZ
^ End(1) ^
BBB01BB ZBB01 BZ
^ End(1) ^
BBB01BB ZBB0 1BZ
^ Check(1) ^
BBB0BBB ZBB 0BBZ
^ IsFin ^
BBB0BBB ZB B0BBZ
^ Start ^
BBB0BBB ZBB 0BBZ
^ initial ^
BBBBBBB ZBBB BBZ
^ End(0) ^
BBBBBBB ZBB BBBZ
^ Check(0) ^
BBBBBBB ZBB BBBZ
^ halt-accept ^
Основываясь на этом примере, я думаю, что конструкциякорректный DPDA с двумя стеками эквивалентен машинам Тьюринга.Поэтому NPDA является подмножеством или равно 2-стека DPDA.