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.