Производит КПК признать следующую формулировку: язык строк, содержащих больше, чем БPDA принять язык строк, содержащих больше, чем Б
я боролся с этим вопросом в течение нескольких дней, я, кажется, ударил полный ментальный блок. Кто-нибудь сможет дать некоторые рекомендации или указания, как я могу решить эту проблему?
Я предполагаю, что вы имеете в виду строки a^nb^m, где n>m.
Идея относительно легко, для a вы толкаете его на стеке (в цикле), для b переключения на отдельный цикл поп a из стека. Если стек всегда пуст, вы отказываетесь от FAIL. Если в первом цикле вы получаете что-либо кроме a или b, или во втором цикле вы получаете что-либо кроме b, вы отказываетесь от FAIL.
В конце вы пытаетесь попом другого a и если стек пуст вы отказываетесь с FAIL (то есть, вы, по крайней мере, столько b 's как a-й в стеке, возможно, больше). Если нет, УСПЕХ.
Редактировать: Как примечание, я не уверен, что это правильный сайт для этого вопроса, может быть, лучше для программистов. Не уверен, хотя и не голосовал за закрытие.
Ваша проблема с "more a a b's" может быть решена с помощью PDA.
Все, что вам нужно сделать, это:
При входе a и стек либо пусто, либо имеет a на вершине, нажмите a в стеке; pop b, если b - наверх.
При вводе b, а стек либо пуст, либо сверху имеет b, толкает b на стек; pop a, если a находится на вершине.
Наконец, когда строка закончена, перейдите в конечное состояние с нулевым вводом, если a находится поверх стека. В противном случае у вас больше нет a, а не b.
Ваше предложение работает, если у вас есть более infront of b и если строка заканчивается на a. Однако он терпит неудачу, когда строка заканчивается на «b», или если строка имеет «b» infront of «a» , например, bbbaaaa потерпит неудачу, а baaaaab также потерпит неудачу Любые предложения? – user1301430
Да, но тогда этот язык больше не является CFG, не так ли? – Blindy
Спасибо за помощь, еще один вопрос. Какие вариации строк будут приняты КПК для этой проблемы, и какие из них он отклонит. Я был в предположении, что он может принимать любые вариации a и b, если в строке больше a, чем b. Спасибо – user1301430