CNF significa forma normal de Chomsky. Una CFG (gramàtica lliure de context) està en CNF (forma normal de Chomsky) si totes les regles de producció compleixen una de les condicions següents:
- Símbol d'inici generant ε Per exemple, A → ε.
- Un no terminal que genera dos no terminals. Per exemple, S → AB.
- Un no terminal que genera un terminal. Per exemple, S → a.
Per exemple:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} Les regles de producció de la gramàtica G1 compleixen les regles especificades per a CNF, de manera que la gramàtica G1 està en CNF. Tanmateix, la regla de producció de la gramàtica G2 no compleix les regles especificades per a CNF ja que S → aZ conté terminal seguit de no terminal. Per tant, la gramàtica G2 no està en CNF.
jvm en java
Passos per convertir CFG en CNF
Pas 1: Elimineu el símbol d'inici del RHS. Si el símbol d'inici T es troba a la part dreta de qualsevol producció, creeu una nova producció com:
S1 → S
On S1 és el nou símbol d'inici.
Pas 2: A la gramàtica, elimina les produccions nul·les, unitàries i inútils. Podeu consultar la Simplificació de CFG.
Pas 3: Eliminar terminals del RHS de la producció si existeixen amb altres no terminals o terminals. Per exemple, la producció S → aA es pot descompondre com:
numpy linspace
S → RA R → a
Pas 4: Elimineu RHS amb més de dos no terminals. Per exemple, S → ASB es pot descompondre com:
S → RS R → AS
Exemple:
Converteix el CFG donat a CNF. Considereu la gramàtica donada G1:
S → a | aA | B A → aBB | ε B → Aa | b
Solució:
Pas 1: Crearem una nova producció S1 → S, ja que el símbol d'inici S apareix a l'RHS. La gramàtica serà:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
Pas 2: Com que la gramàtica G1 conté A → ε producció nul·la, la seva eliminació de la gramàtica produeix:
salvar de
S1 → S S → a | aA | B A → aBB B → Aa | b | a
Ara, com que la gramàtica G1 conté la producció unitat S → B, el seu rendiment d'eliminació:
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
També elimina la unitat de producció S1 → S, la seva eliminació de la gramàtica dóna:
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
Pas 3: En la regla de producció S0 → aA | Aa, S → aA | Aa, A → aBB i B → Aa, el terminal a existeix a RHS amb no terminals. Per tant, substituirem la terminal a per X:
matriu java de cadena
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
Pas 4: A la regla de producció A → XBB, RHS té més de dos símbols, eliminant-lo del rendiment gramatical:
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
Per tant, per a la gramàtica donada, aquest és el CNF requerit.