Предположим, у вас есть КПК, который полагается на загрузку нескольких значений в стек. В частности, в состоянии q с символом x верхней части стека и входным символом y вы заменяете символ x строкой s (которая может сохранять или не поддерживать x в своей позиции в стеке) и переходите в состояние q '.
Этот КПК может быть преобразован в тот, который не требует одновременной загрузки нескольких символов в стек следующим образом:
- добавляет состояния q1, q2,…, q | s | на КПК
- изменить переход (q, x, y) -> (q ', s) на (q, x, y) -> (q1, s [1])
- добавить переходы (qk, x, e) -> (qk + 1, s [2] x) для 1 <= k <s </li>
- добавить переход (q | s |, x, e) - > (q ', x)
Обратите внимание, что если мы начали с DPDA, у нас все еще есть DPDA после этого преобразования: у нас есть переходы, которые не потребляют входные данные, однако это хорошо для DPDA до тех пор, пока в любой момент времени может быть выполнен только один переход.
Поппинг немного сложнее, но идея та же:
- вводит некоторые новые состояния
- начинайте вставлять символы в правильном порядке
- если вы выталкиваете все, что вам нужно, отлично, продолжайте, как в оригинальном КПК
- , если вы обнаружите, что упускаете что-то, что хотели выложить, в основном вам нужно просто взломать sh (DPDA не может принять входные данные, поскольку он только пошел по этому пути, потому что должен был, в то время как NPDA все еще может принимать по другому пути)