Автоматы и арифметические выражения

Question

Я пытаюсь выяснить, как сделать арифметические выражения в Pushdown Automata?(PDA), например, L=W|W= Bm Cn-m. Что я думаю сделать, это нажать As, затем pop Bs, а затем либо pop As. C или B с C в зависимости от того, что осталось. Например, aaabbc (нажмите aaa, затем нажмите Bs bba, а затем либо нажмите A с C или B с C, в зависимости от того, какой из них больше.

Answer 1

За слово w чтобы быть на языке, он должен иметь n>=m по вашему определению (иначе C^(n-m) отрицательно, и это невозможно).

Итак, ваш автомат в основном должен:

1. Нажмите, чтобы сложить, когда видите "а"
2. выскочить из стека, увидев "б"
3. выскочить из стека, увидев "с".

Также некоторые важные вопросы:

• Вы должны перемещаться между различными состояниями, когда видите "нового" персонажа.
• Ваш автомат должен принять w=eps (пустое слово).
• w=a^b b^n также на языке, убедитесь, что вы позаботитесь об этом.

Я надеюсь, что дал вам достаточно хороших указаний, чтобы решить это самостоятельно..

Удачи!