КПК принимает язык строк, содержащий больше а, чем б

Question

Создание КПК для распознавания следующего языка: язык строк, содержащих больше а, чем b

Я уже несколько дней бьюсь над этим вопросом, похоже, у меня полная психическая блокада. Сможет ли кто-нибудь дать какое-нибудь руководство или руководство, как я могу решить эту проблему?

Answer 1

Ваша проблема "больше а чем б" может быть решена с помощью КПК.

Все, что вам нужно сделать, это:

• Если для ввода задано значение a, а стек либо пуст, либо имеет a сверху, нажмите a в стеке; pop b, если b - вершина.

• Когда ввод равен b и стек либо пуст, либо имеет b вверху, нажмите b в стеке; pop a, если a сверху.

• Наконец, когда строка закончена, перейдите в конечное состояние с нулевым вводом, если a находится на вершине стека. В противном случае у вас не будет больше a, чем b.

Answer 2

Основная информация о транзакции приведена на рисунке ниже.

Вот полная транзакция.

В ней equal равно NULL. $ знак помещается в стекв начале строки и поп в конце, чтобы определить, что строка полностью прочитана и теперь заканчивается. qo - это начальное состояние, а q5 - конечное состояние.

Это недетерминированные автоматы нажатия вниз (NPDA). Так что из-за NPDA транзакция строки отклонения не отображается,

Answer 3

Я предложил более общее решение проблемы, касающейся числа as и bs, см. Рисунок ниже:

, где a> b означает больше, чем bs, и a Z означает дно стека, а A / B - символы стека.

Я взволнован этим, потому что этот КПК разделяет 3 различных состояния. В вашей задаче вы можете просто установить состояние a> b как конечное состояние и позволить a = b быть начальным состоянием.

И если вы хотите пойти дальше, вы можете использовать этот КПК, чтобы с легкостью генерировать КПК для a> = b, a - b> = 1, 2 <= a - b <= 3 и т. Д., Что очень интересно. </p>

Answer 4

Я предполагаю, что вы имеете в виду строки вида a^nb^m, где n> m.

Идея относительно проста: a вы кладете ее в стек (вцикл *), для b вы переключаетесь на отдельный цикл для выталкивания a из стека.Если стек пуст, вы отказываетесь от FAIL.Если в первом цикле вы получаете что-то отличное от a или b, или во втором цикле вы получаете что-то отличное от b, вы отказываетесь от FAIL.

В конце вы пытаетесьвставьте еще один a, и если стек пуст, вы сдаете с ошибкой (т. е. у вас было хотя бы столько b, сколько a в стеке, возможно, больше).Если нет, УСПЕХ.

Редактировать: Как примечание, я не уверен, что это правильный сайт для этого вопроса, может быть лучше для программистов.Не уверен, хотя и не голосую, чтобы закрыть.