Forma normale di Chomsky

Un CFG è in forma normale di Chomsky se le produzioni sono nelle seguenti forme:

• A → a
• A → BC
• S → ε

dove A, B e C sono non terminali e a è terminale.

Algoritmo per convertire in forma normale di Chomsky -

Step 1 - Se il simbolo di avvio S si verifica su un lato destro, crea un nuovo simbolo di inizio S’ e una nuova produzione S’→ S.

Step 2- Rimuovi le produzioni Null. (Utilizzo dell'algoritmo di rimozione della produzione Null discusso in precedenza)

Step 3- Rimuovere le produzioni unitarie. (Utilizzo dell'algoritmo di rimozione della produzione unitaria discusso in precedenza)

Step 4 - Sostituisci ogni produzione A → B₁…B_n dove n > 2 con A → B₁C dove C → B₂ …B_n. Ripetere questo passaggio per tutte le produzioni con due o più simboli sul lato destro.

Step 5 - Se il lato destro di qualsiasi produzione è nella forma A → aB dove a è un terminale e A, B non sono terminali, quindi la produzione viene sostituita da A → XB e X → a. Ripeti questo passaggio per ogni produzione che si trova nella formaA → aB.

Problema

Converti il ​​seguente CFG in CNF

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

Soluzione

(1) Da S appare in RHS, aggiungiamo un nuovo stato S₀ e S₀→S viene aggiunto al set di produzione e diventa -

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

(2) Ora rimuoveremo le produzioni nulle -

B → ∈ e A → ∈

Dopo aver rimosso B → ε, l'insieme di produzione diventa -

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

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

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

(3) Ora rimuoveremo le produzioni unitarie.

Dopo aver rimosso S → S, il set di produzione diventa -

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

Dopo aver rimosso S ₀ → S, il set di produzione diventa -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

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

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | b

B → b

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

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

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

(4) Ora scopriremo più di due variabili nella RHS

Qui, S ₀ → ASA, S → ASA, A → ASA viola due non terminali in RHS

Quindi applicheremo il passaggio 4 e il passaggio 5 per ottenere il seguente set di produzione finale che è in CNF -

S ₀ → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Dobbiamo cambiare le produzioni S ₀ → aB, S → aB, A → aB

E il set di produzione finale diventa -

S ₀ → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a