Какие типы языков принимаются PDA, в которых размер стека ограничен, скажем, 20 предметов?Какие языки принимаются КПК, в которых размер стека ограничен?
На мой взгляд, он все равно должен быть CFL, потому что есть временная память для хранения.
КПК с стеком, ограниченным содержанием 20 элементов, эквивалентен DFA. Вот доказательство.
Возьмите любой КПК-20, и вы можете превратить его в эквивалентный DFA. Скажем, алфавит стека S, где | S | = N. У вас также есть символ Z нижнего стека. Мы представляем дополнительный символ, который мы также можем иметь в стеке, что означает «неиспользуемый». Стек теперь эквивалентна строке формы x = - * S * Z, где | x | = 20, во всех случаях. Нажатие на стек состоит в замене вхождений -, тогда как popping заключается в замене других символов на -, в LIFO. Есть теперь (N + 2)^20 возможных конфигураций стека для любого КПК-20. Чтобы построить DFA, просто повторите каждое состояние DFA этим фактором и переходы в состояния DFA отражают новую конфигурацию стека. Таким образом, информация, содержащаяся в конфигурации стека в КПК-20, содержится в текущем состоянии DFA.
Возьмите любой DFA, и вы можете превратить его в эквивалентный КПК-20. Просто не используйте стек, и у вас есть КПК-20, который принимает тот же язык, что и DFA.
Просто, чтобы проиллюстрировать первую часть доказательства, рассмотрит PDA-5 с состояниями A, B, C, ..., Z, и много переходов. Предположим, что входной алфавит равен {0, 1}. Например, есть 2^5 = 32 различных конфигураций стека. DFA, эквивалентный этому КПК-5, может иметь состояния A1, B1, ..., Z1, A2, B2, ..., Z2, ..., A32, B32, ..., Z32, хотя он будет иметь такое же количество переходов, что и оригинал. Если переход в исходном КПК-5 перенесет стек из конфигурации №2 в состоянии R в конфигурацию № 17, а машина в состояние F, DFA перейдет из состояния R2 в состояние F17.
Как вы получили (N + 2)^20 конфигураций для стека? А позже вы сказали 2^5 конфигураций стека, когда input set = {0, 1}. Разве нет рассогласования? – user3330840
@ user330840 Я думаю, что вы правы, читая его, формулы неточны и непоследовательны. Тем не менее, я думаю, что это все еще достаточно иллюстративно, чтобы продемонстрировать тезис, т. Е. Существует множество конфигураций стека с не более чем 20 символами. (N + 2)^20 является верхней границей, которая не может быть достигнута. 2^5 может быть не совсем корректным для КПК-5 либо потому, что он не учитывает короткие стеки; 3^5, вероятно, ближе. – Patrick87
Если вас интересует такой вопрос, пожалуйста, подтвердите поддержку нового форума компьютерных наук, сделав по адресу http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer= rpnXA1_2BNYzXN85c5ibxQ2 – Patrick87