Какие типы языков принимаются КПК, в которых размер стека ограничен?
1 ответ
КПК с ограниченным стеком, состоящим из 20 элементов, эквивалентен DFA. Вот доказательство.
Возьмите любой КПК-20, и вы сможете превратить его в эквивалент DFA. Допустим, алфавит стека S, где |S| = N. У вас также есть символ нижней части стека Z. Мы представляем дополнительный символ -, который мы также можем иметь в стеке, который обозначает "неиспользованный". Стек теперь эквивалентен строке вида x = -* S* Z, где |x| = 20, во всех случаях. Вставка в стек состоит в замене вхождений -, в то время как выталкивание - в замене других символов на - в стиле LIFO. Теперь есть (N+2)^20 возможных конфигураций стека для любого КПК-20. Чтобы построить DFA, просто реплицируйте каждое состояние DFA по этому фактору, и переходы в состояния DFA отражают новую конфигурацию стека. Таким образом, информация, содержащаяся в конфигурации стека в PDA-20, содержится в текущем состоянии DFA.
Возьмите любой DFA, и вы сможете превратить его в эквивалентный PDA-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.