logo

Forma normale di Chomsky (CNF)

CNF sta per forma normale di Chomsky. Una CFG (grammatica libera dal contesto) è in CNF (forma normale di Chomsky) se tutte le regole di produzione soddisfano una delle seguenti condizioni:

  • Inizia il simbolo che genera ε Ad esempio, A → ε.
  • Un non terminale che genera due non terminali. Ad esempio, S → AB.
  • Un non terminale che genera un terminale. Ad esempio, S → a.

Per esempio:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

Le regole di produzione della Grammatica G1 soddisfano le regole specificate per CNF, quindi la grammatica G1 è in CNF. Tuttavia, la regola di produzione della Grammatica G2 non soddisfa le regole specificate per CNF in quanto S → aZ contiene terminale seguito da non terminale. Quindi la grammatica G2 non è presente nel CNF.

metodi in Java

Passaggi per convertire CFG in CNF

Passo 1: Eliminare il simbolo di partenza dalla destra. Se il simbolo di inizio T si trova sul lato destro di qualsiasi produzione, crea una nuova produzione come:

 S1 → S 

Dove S1 è il nuovo simbolo di inizio.

Passo 2: Nella grammatica eliminare le produzioni nulle, unitarie e inutili. È possibile fare riferimento alla Semplificazione del CFG.

Passaggio 3: Eliminare i terminali dal lato destro della produzione se esistono con altri non terminali o terminali. Ad esempio, la produzione S → aA può essere scomposta come:

arraylist Java ordinato
 S → RA R → a 

Passaggio 4: Elimina RHS con più di due non terminali. Ad esempio, S → ASB può essere scomposto come:

 S → RS R → AS 

Esempio:

Converti il ​​CFG indicato in CNF. Considera la grammatica G1 data:

 S → a | aA | B A → aBB | ε B → Aa | b 

Soluzione:

Passo 1: Creeremo una nuova produzione S1 → S, poiché il simbolo di inizio S appare sul lato destro. La grammatica sarà:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Passo 2: Poiché la grammatica G1 contiene una produzione A → ε nulla, la sua rimozione dalla grammatica produce:

stringa in carattere java
 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Ora, poiché la grammatica G1 contiene Produzione unitaria S → B, la sua resa di rimozione:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

Togliendo anche la produzione unitaria S1 → S, la sua rimozione dalla grammatica dà:

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Passaggio 3: Nella regola di produzione S0 → aA | Aa, S → aA | Aa, A → aBB e B → Aa, il terminale a esiste su RHS con non terminali. Quindi sostituiremo il terminale a con X:

quanti 0 su un miliardo
 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Passaggio 4: Nella regola di produzione A → XBB, RHS ha più di due simboli, rimuovendolo dalla resa grammaticale:

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Quindi, per la grammatica data, questo è il CNF richiesto.