les automates à pile et les expressions arithmétiques

Question

J'essaie de comprendre comment faire des expressions arithmétiques dans Pushdown Automata? (PDA) par exemple L = W | W = An Bm Cn-m Ce que je pense faire est de pousser As puis pop Bs, puis pop comme avec C ou Bs avec C en fonction de ce qui reste. Par exemple aaabbc (en poussant aaa puis en sautant avec Bs bba et ensuite en sautant A avec C ou B avec C selon lequel est le plus grand

Answer 1

Pour qu'un mot w soit dans la langue, il doit y avoir n>=m par définition (sinon C^(n-m) est négatif, et c'est impossible)

Ainsi, votre automate a besoin essentiellement à:.

1. push-to-pile en voyant 'une'
2. pop de la pile en voyant 'b'
3. pop de la pile en voyant «c».

En outre, certaines questions importantes:

• Vous devez vous déplacer entre les différents états en voyant un caractère « nouveau » . Votre automate doit accepter le w=eps (mot vide).
• w=a^b b^n est également dans la langue, assurez-vous de prendre soin de cela.

J'espère que je vous ai donné assez bon conduit à le résoudre vous-même ..

Bonne chance!