КПК со стеком, ограниченным 20 предметами, эквивалентен DFA. Вот доказательство.
Возьмите любой КПК-20, и вы сможете превратить его в эквивалентный DFA. Допустим, алфавит стека S, где | S | = N. У вас также есть символ нижней части стека Z. Мы представляем дополнительный символ -, который мы также можем иметь в стеке, что означает «неиспользованный». Стек теперь эквивалентен строке вида x = - * S * Z, где | x | = 20, во всех случаях. Выталкивание в стек состоит в замене вхождений -, в то время как выталкивание - в замене других символов на - способом LIFO. Теперь есть (N + 2) ^ 20 возможных конфигураций стека для любого КПК-20. Чтобы построить DFA, просто реплицируйте каждое состояние DFA по этому фактору, и переходы в состояния DFA отражают новую конфигурацию стека. Таким образом, информация, содержащаяся в конфигурации стека в КПК-20, содержится в текущем состоянии DFA.
Возьмите любой DFA, и вы сможете превратить его в эквивалентный КПК-20. Просто не используйте стек, и у вас есть PDA-20, который принимает тот же язык, что и DFA.
Просто для иллюстрации первой части доказательства рассмотрим КПК-5 с состояниями A, B, C, ..., Z и множеством переходов. Допустим, входной алфавит {0, 1}. Тогда есть 2 ^ 5 = 32 различных конфигураций стека, скажем. DFA, эквивалентный этому PDA-5, может иметь состояния A1, B1, ..., Z1, A2, B2, ..., Z2, ..., A32, B32, ..., Z32, хотя он будет иметь столько же переходов, сколько и оригинал. Если переход в исходном КПК-5 перенес бы стек из конфигурации # 2 в состоянии R в конфигурацию # 17 и машину в состояние F, DFA перейдет из состояния R2 в состояние F17.