Simplification CFG

Dans un CFG, il peut arriver que toutes les règles et symboles de production ne soient pas nécessaires pour la dérivation des chaînes. En outre, il peut y avoir des productions nulles et des productions unitaires. L'élimination de ces productions et symboles est appeléesimplification of CFGs. La simplification comprend essentiellement les étapes suivantes -

  • Réduction de CFG
  • Suppression des productions unitaires
  • Suppression des productions nulles

Réduction de CFG

Les CFG sont réduits en deux phases -

Phase 1 - Dérivation d'une grammaire équivalente, G’, du CFG, G, de sorte que chaque variable dérive une chaîne terminale.

Derivation Procedure -

Étape 1 - Inclure tous les symboles, W1, qui dérivent un terminal et initialisent i=1.

Étape 2 - Incluez tous les symboles, Wi+1, qui dérivent Wi.

Étape 3 - Incrément i et répétez l'étape 2, jusqu'à Wi+1 = Wi.

Étape 4 - Incluez toutes les règles de production qui ont Wi dedans.

Phase 2 - Dérivation d'une grammaire équivalente, G”, du CFG, G’, de sorte que chaque symbole apparaisse sous une forme sententielle.

Derivation Procedure -

Étape 1 - Incluez le symbole de départ dans Y1 et initialiser i = 1.

Étape 2 - Incluez tous les symboles, Yi+1, qui peut être dérivé de Yi et inclure toutes les règles de production qui ont été appliquées.

Étape 3 - Incrément i et répétez l'étape 2, jusqu'à Yi+1 = Yi.

Problème

Trouver une grammaire réduite équivalente à la grammaire G, ayant des règles de production, P: S → AC | B, A → a, C → c | BC, E → aA | e

Solution

Phase 1 -

T = {a, c, e}

W 1 = {A, C, E} à partir des règles A → a, C → c et E → aA

W 2 = {A, C, E} U {S} de la règle S → AC

W 3 = {A, C, E, S} U ∅

Puisque W 2 = W 3 , nous pouvons dériver G 'comme -

G '= {{A, C, E, S}, {a, c, e}, P, {S}}

où P: S → AC, A → a, C → c, E → aA | e

Phase 2 -

Y 1 = {S}

Y 2 = {S, A, C} à partir de la règle S → AC

Y 3 = {S, A, C, a, c} à partir des règles A → a et C → c

Y 4 = {S, A, C, a, c}

Puisque Y 3 = Y 4 , on peut dériver G ”comme -

G "= {{A, C, S}, {a, c}, P, {S}}

où P: S → AC, A → a, C → c

Suppression des productions unitaires

Toute règle de production de la forme A → B où A, B ∈ Non-terminal est appelée unit production..

Procédure de retrait -

Step 1 - Pour supprimer A → B, ajouter la production A → x à la règle de grammaire chaque fois B → xse produit dans la grammaire. [x ∈ Terminal, x peut être nul]

Step 2 - Supprimer A → B de la grammaire.

Step 3 - Répétez à partir de l'étape 1 jusqu'à ce que toutes les productions unitaires soient supprimées.

Problem

Supprimer la production unitaire des éléments suivants -

S → XY, X → a, Y → Z | b, Z → M, M → N, N → a

Solution -

Il y a 3 productions unitaires dans la grammaire -

Y → Z, Z → M et M → N

At first, we will remove M → N.

Comme N → a, nous ajoutons M → a, et M → N est supprimé.

L'ensemble de production devient

S → XY, X → a, Y → Z | b, Z → M, M → a, N → a

Now we will remove Z → M.

Comme M → a, nous ajoutons Z → a, et Z → M est supprimé.

L'ensemble de production devient

S → XY, X → a, Y → Z | b, Z → a, M → a, N → a

Now we will remove Y → Z.

Comme Z → a, nous ajoutons Y → a, et Y → Z est supprimé.

L'ensemble de production devient

S → XY, X → a, Y → a | b, Z → a, M → a, N → a

Maintenant, Z, M et N sont inaccessibles, nous pouvons donc les supprimer.

Le CFG final est sans production unitaire -

S → XY, X → a, Y → a | b

Suppression des productions nulles

Dans un CFG, un symbole non terminal ‘A’ est une variable Nullable s'il y a une production A → ε ou il y a une dérivation qui commence à A et finit enfin par

ε: A → .......… → ε

Procédure de retrait

Step 1 - Trouver des variables non terminales nullables qui dérivent ε.

Step 2 - Pour chaque production A → a, construire toutes les productions A → xx est obtenu à partir de ‘a’ en supprimant un ou plusieurs non-terminaux de l'étape 1.

Step 3 - Combinez les productions originales avec le résultat de l'étape 2 et supprimez ε - productions.

Problem

Supprimer la production nulle de ce qui suit -

S → ASA | aB | b, A → B, B → b | ∈

Solution -

Il existe deux variables Nullable - A et B

At first, we will remove B → ε.

Après avoir retiré B → ε, l'ensemble de production devient -

S → ASA | aB | b | a, A ε B | b | & epsilon, B → b

Now we will remove A → ε.

Après avoir retiré A → ε, l'ensemble de production devient -

S → ASA | aB | b | a | SA | AS | S, A → B | b, B → b

Il s'agit de l'ensemble de production final sans transition nulle.