CNF pomeni normalno obliko Chomskyja. CFG (kontekstno prosta slovnica) je v CNF (Chomsky normalna oblika), če vsa produkcijska pravila izpolnjujejo enega od naslednjih pogojev:

• Začni simbol generirati ε. Na primer, A → ε.
• Ne-terminal, ki generira dva ne-terminala. Na primer S → AB.
• Neterminal, ki generira terminal. Na primer S → a.

Na primer:

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

Produkcijska pravila slovnice G1 izpolnjujejo pravila, določena za CNF, zato je slovnica G1 v CNF. Vendar produkcijsko pravilo slovnice G2 ne izpolnjuje pravil, določenih za CNF, saj S → aZ vsebuje terminal, ki mu sledi neterminal. Torej slovnica G2 ni v CNF.

spanje v javascriptu

Koraki za pretvorbo CFG v CNF

Korak 1: Odstranite začetni simbol z RHS. Če je začetni simbol T na desni strani katere koli proizvodnje, ustvarite novo proizvodnjo kot:

 S1 → S 

Kjer je S1 nov začetni simbol.

2. korak: V slovnici odstranite ničelne, enotne in neuporabne produkcije. Lahko se sklicujete na poenostavitev CFG.

3. korak: Odstranite terminale iz RHS proizvodnje, če obstajajo z drugimi ne-terminali ali terminali. Na primer, proizvodnjo S → aA je mogoče razstaviti kot:

 S → RA R → a 

4. korak: Odstranite RHS z več kot dvema neterminaloma. Na primer, S → ASB je mogoče razstaviti kot:

 S → RS R → AS 

primer:

Pretvorite podani CFG v CNF. Razmislite o dani slovnici G1:

binarno drevo

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

rešitev:

Korak 1: Ustvarili bomo novo proizvodnjo S1 → S, saj se na RHS pojavi začetni simbol S. Slovnica bo:

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

2. korak: Ker slovnica G1 vsebuje A → ε ničelno produkcijo, njena odstranitev iz slovnice daje:

govinda

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

Zdaj, ker slovnica G1 vsebuje proizvodnjo enote S → B, njena odstranitev prinaša:

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

Odstranite tudi proizvodnjo enote S1 → S, njena odstranitev iz slovnice daje:

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

3. korak: V proizvodnem pravilu S0 → aA | Aa, S → aA | Aa, A → aBB in B → Aa, terminal a obstaja na RHS z neterminali. Tako bomo zamenjali terminal a z X:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

4. korak: V produkcijskem pravilu A → XBB ima RHS več kot dva simbola, kar ga odstrani iz slovničnega donosa:

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

Zato je za dano slovnico to zahtevana CNF.

testiranje in vrste testiranja