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