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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

где a > b означает больше, чем bs, и то же самое делает a

Z означает дно стека, а A/B - символы стека.

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

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

Answer 3

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

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

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

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

Answer 4

КПК принимает больше а, чем б

https://s tackru.com/images/1c9e9831d398ac0c8590472b7694139198d9ae38.jpg

Answer 5

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

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

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

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