Introduction aux automates pushdown

Structure de base du PDA

Un automate pushdown est un moyen d'implémenter une grammaire sans contexte de la même manière que nous concevons DFA pour une grammaire régulière. Un DFA peut mémoriser une quantité limitée d'informations, mais un PDA peut mémoriser une quantité infinie d'informations.

Fondamentalement, un automate pushdown est -

"Finite state machine" + "a stack"

Un automate pushdown a trois composants -

• une bande d'entrée,
• une unité de commande, et
• une pile de taille infinie.

La tête de pile scanne le symbole supérieur de la pile.

Une pile effectue deux opérations -

• Push - un nouveau symbole est ajouté en haut.

• Pop - le symbole du haut est lu et supprimé.

Un PDA peut ou non lire un symbole d'entrée, mais il doit lire le haut de la pile à chaque transition.

Un PDA peut être formellement décrit comme un 7-tuple (Q, ∑, S, δ, q ₀ , I, F) -

• Q est le nombre fini d'états

• ∑ est l'alphabet d'entrée

• S est des symboles de pile

• δ est la fonction de transition: Q × (∑ ∪ {ε}) × S × Q × S *

• q₀est l'état initial (q ₀ ∈ Q)

• I est le symbole initial du haut de la pile (I ∈ S)

• F est un ensemble d'états acceptants (F ∈ Q)

Le diagramme suivant montre une transition dans un PDA d'un état q ₁ à un état q ₂ , étiqueté comme a, b → c -

Cela signifie à l'état q₁, si nous rencontrons une chaîne d'entrée ‘a’ et le symbole du haut de la pile est ‘b’, puis on pop ‘b’, pousser ‘c’ au-dessus de la pile et passer à l'état q₂.

Terminologies liées aux PDA

Description instantanée

La description instantanée (ID) d'un PDA est représentée par un triplet (q, w, s) où

• q est l'état

• w est une entrée non consommée

• s est le contenu de la pile

Notation de tourniquet

La notation "tourniquet" est utilisée pour connecter des paires d'identifiants qui représentent un ou plusieurs mouvements d'un PDA. Le processus de transition est indiqué par le symbole de tourniquet "⊢".

Considérons un PDA (Q, ∑, S, δ, q ₀ , I, F). Une transition peut être représentée mathématiquement par la notation de tourniquet suivante -

(p, aw, Tβ) ⊢ (q, w, αb)

Cela implique que tout en prenant une transition d'état p établir q, le symbole d'entrée ‘a’ est consommé, et le haut de la pile ‘T’ est remplacé par une nouvelle chaîne ‘α’.

Note - Si nous voulons zéro ou plusieurs mouvements d'un PDA, nous devons utiliser le symbole (⊢ *) pour cela.