Les automates a pile ne sont pas beaucoup plus compliques quel les FSM. Tu as des operations sur chaque etat qui push ou qui pop l'etat courant dans la pile (donc globale) de l'automate. De meme, les transitions doivent supporter des testes sur l'etat de la pile (Est-elle vide ? Quel est le dernier etat ? Quels sont les n derniers etats ?). Ainsi tu peux reconnaitre des langages du type anbn alors que tu ne pouvais pas avec des automates finis.
L'automates pour ce dernier exemple est construit facilement. On lit des a en pushant l'etat dans la pile. Puis on lit que des b en poppant la pile. On acceptera le mot si la pile est vide et qu'il n'y a plus de lettre a lire.
[^] # Re: automates à pile
Posté par Vash . En réponse à la dépêche Pourquoi les développeurs n'utilisent pas plus de machines à état ?. Évalué à 3.
Les automates a pile ne sont pas beaucoup plus compliques quel les FSM. Tu as des operations sur chaque etat qui push ou qui pop l'etat courant dans la pile (donc globale) de l'automate. De meme, les transitions doivent supporter des testes sur l'etat de la pile (Est-elle vide ? Quel est le dernier etat ? Quels sont les n derniers etats ?). Ainsi tu peux reconnaitre des langages du type anbn alors que tu ne pouvais pas avec des automates finis.
L'automates pour ce dernier exemple est construit facilement. On lit des a en pushant l'etat dans la pile. Puis on lit que des b en poppant la pile. On acceptera le mot si la pile est vide et qu'il n'y a plus de lettre a lire.