PDA et grammaire sans contexte
Si une grammaire G est sans contexte, nous pouvons construire un PDA non déterministe équivalent qui accepte le langage produit par la grammaire sans contexte G. Un analyseur peut être construit pour la grammaireG.
Également si P est un automate pushdown, une grammaire équivalente sans contexte G peut être construite où
L(G) = L(P)
Dans les deux sujets suivants, nous discuterons de la conversion de PDA en CFG et vice versa.
Algorithme pour trouver le PDA correspondant à un CFG donné
Input - A CFG, G = (V, T, P, S)
Output- PDA équivalent, P = (Q, ∑, S, δ, q 0 , I, F)
Step 1 - Convertir les productions du CFG en GNF.
Step 2 - Le PDA n'aura qu'un seul état {q}.
Step 3 - Le symbole de départ de CFG sera le symbole de départ dans le PDA.
Step 4 - Tous les non-terminaux du CFG seront les symboles de pile du PDA et tous les terminaux du CFG seront les symboles d'entrée du PDA.
Step 5 - Pour chaque production sous la forme A → aX où a est terminal et A, X sont une combinaison de terminaux et de non-terminaux, faites une transition δ (q, a, A).
Problème
Construisez un PDA à partir du CFG suivant.
G = ({S, X}, {a, b}, P, S)
où sont les productions -
S → XS | ε , A → aXb | Ab | ab
Solution
Soit le PDA équivalent,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
où δ -
δ (q, ε, S) = {(q, XS), (q, ε)}
δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)}
Algorithme pour trouver CFG correspondant à un PDA donné
Input - A CFG, G = (V, T, P, S)
Output- PDA équivalent, P = (Q, ∑, S, δ, q 0 , I, F) tel que les non-terminaux de la grammaire G seront {X wx | w, x ∈ Q} et l'état de départ sera un q0, F .
Step 1- Pour tout w, x, y, z ∈ Q, m ∈ S et a, b ∈ ∑, si δ (w, a, ε) contient (y, m) et (z, b, m) contient (x, ε), ajoutez la règle de production X wx → a X yz b dans la grammaire G.
Step 2- Pour tout w, x, y, z ∈ Q, ajoutez la règle de production X wx → X wy X yx dans la grammaire G.
Step 3- Pour w ∈ Q, ajoutez la règle de production X ww → ε dans la grammaire G.