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.