Semplificazione CFG

In un CFG, può accadere che tutte le regole e simboli di produzione non siano necessari per la derivazione di stringhe. Inoltre, potrebbero esserci alcune produzioni nulle e produzioni unitarie. Viene chiamata l'eliminazione di queste produzioni e simbolisimplification of CFGs. La semplificazione comprende essenzialmente i seguenti passaggi:

• Riduzione di CFG
• Rimozione delle produzioni unitarie
• Rimozione di produzioni nulle

Riduzione di CFG

I CFG vengono ridotti in due fasi:

Phase 1 - Derivazione di una grammatica equivalente, G’, dal CFG, G, in modo tale che ogni variabile derivi una stringa terminale.

Derivation Procedure -

Passaggio 1: includi tutti i simboli, W₁, che derivano un terminale e inizializzano i=1.

Passaggio 2: includi tutti i simboli, W_i+1, che derivano W_i.

Passaggio 3: incremento i e ripetere il passaggio 2, finché W_i+1 = W_i.

Passaggio 4: includere tutte le regole di produzione che hanno W_i dentro.

Phase 2 - Derivazione di una grammatica equivalente, G”, dal CFG, G’, in modo tale che ogni simbolo appaia in una forma sentenziale.

Derivation Procedure -

Passaggio 1: includere il simbolo di inizio in Y₁ e inizializza i = 1.

Passaggio 2: includi tutti i simboli, Y_i+1, che può essere derivato da Y_i e includere tutte le regole di produzione che sono state applicate.

Passaggio 3: incremento i e ripetere il passaggio 2, finché Y_i+1 = Y_i.

Problema

Trova una grammatica ridotta equivalente alla grammatica G, con regole di produzione, P: S → AC | B, A → a, C → c | BC, E → aA | e

Soluzione

Phase 1 -

T = {a, c, e}

W ₁ = {A, C, E} dalle regole A → a, C → ce E → aA

W ₂ = {A, C, E} U {S} dalla regola S → AC

W ₃ = {LA, DO, MI, S} U ∅

Poiché W ₂ = W ₃ , possiamo derivare G 'come -

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

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

Phase 2 -

Y ₁ = {S}

Y ₂ = {S, A, C} dalla regola S → AC

Y ₃ = {S, A, C, a, c} dalle regole A → a e C → c

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

Poiché Y ₃ = Y ₄ , possiamo derivare G "come -

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

dove P: S → AC, A → a, C → c

Rimozione delle produzioni unitarie

Qualsiasi regola di produzione nella forma A → B dove viene chiamata A, B ∈ Non terminale unit production..

Procedura di rimozione -

Step 1 - Per rimuovere A → B, aggiungi produzione A → x alla regola grammaticale ogni volta B → xsi verifica nella grammatica. [x ∈ Terminal, x può essere Null]

Step 2 - Elimina A → B dalla grammatica.

Step 3 - Ripetere dal passaggio 1 fino a quando tutte le produzioni di unità vengono rimosse.

Problem

Rimuovere la produzione unitaria da quanto segue:

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

Solution -

Ci sono 3 produzioni unitarie nella grammatica:

Y → Z, Z → M e M → N

At first, we will remove M → N.

Come N → a, aggiungiamo M → a e M → N viene rimosso.

Il set di produzione diventa

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

Now we will remove Z → M.

Come M → a, aggiungiamo Z → a e Z → M viene rimosso.

Il set di produzione diventa

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

Now we will remove Y → Z.

Come Z → a, aggiungiamo Y → a e Y → Z viene rimosso.

Il set di produzione diventa

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

Ora Z, M e N sono irraggiungibili, quindi possiamo rimuoverli.

Il CFG finale è privo di produzione unitaria -

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

Rimozione di produzioni nulle

In un CFG, un simbolo non terminale ‘A’ è una variabile nullable se c'è una produzione A → ε o c'è una derivazione che inizia da A e alla fine finisce con

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

Procedura di rimozione

Step 1 - Trova variabili non terminali nullable che derivano ε.

Step 2 - Per ogni produzione A → a, costruisci tutte le produzioni A → x dove x è ottenuto da ‘a’ rimuovendo uno o più non terminali dal passaggio 1.

Step 3 - Combina le produzioni originali con il risultato del passaggio 2 e rimuovi ε - productions.

Problem

Rimuovi la produzione nulla da quanto segue:

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

Solution -

Sono presenti due variabili nullable: A e B

At first, we will remove B → ε.

Dopo aver rimosso B → ε, il set di produzione diventa -

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

Now we will remove A → ε.

Dopo aver rimosso A → ε, il set di produzione diventa -

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

Questo è il set di produzione finale senza transizione nulla.