A CNF a Chomsky normál formát jelenti. A CFG (kontextusmentes nyelvtan) CNF (Chomsky normál formában) van, ha minden termelési szabály megfelel a következő feltételek egyikének:

• Indítsa el az ε szimbólum generálását. Például A → ε.
• Egy nem terminál, amely két nem terminált generál. Például S → AB.
• Terminált generáló nem terminál. Például S → a.

Például:

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

A G1 nyelvtan előállítási szabályai megfelelnek a CNF-re meghatározott szabályoknak, így a G1 nyelvtan CNF-ben van. A Grammar G2 előállítási szabálya azonban nem felel meg a CNF-re meghatározott szabályoknak, mivel az S → aZ terminált, majd nem terminált tartalmaz. Tehát a G2 nyelvtan nincs a CNF-ben.

keresse meg a c++ térképen

A CFG CNF-vé alakításának lépései

1. lépés: Távolítsa el a start szimbólumot az RHS-ből. Ha a T kezdőszimbólum bármely produkció jobb oldalán található, hozzon létre egy új produkciót a következőképpen:

 S1 → S 

Ahol S1 az új kezdő szimbólum.

2. lépés: A nyelvtanból távolítsa el a null, unit és haszontalan produkciókat. Olvassa el a CFG egyszerűsítését.

3. lépés: Távolítsa el a terminálokat a gyártás RHS-éből, ha léteznek más nem terminálokkal vagy terminálokkal. Például az S → aA termelés a következőképpen bontható fel:

 S → RA R → a 

4. lépés: Szüntesse meg az RHS-t kettőnél több nem terminállal. Például az S → ASB a következőképpen bontható fel:

 S → RS R → AS 

Példa:

Konvertálja a megadott CFG-t CNF-re. Tekintsük a megadott G1 nyelvtant:

összefűzési karakterlánc java-ban

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

Megoldás:

1. lépés: Létrehozunk egy új S1 → S produkciót, mivel az S start szimbólum megjelenik az RHS-en. A nyelvtan a következő lesz:

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

2. lépés: Mivel a G1 nyelvtan A → ε null produkciót tartalmaz, a nyelvtanból való eltávolítása a következőket eredményezi:

középső css gomb

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

Most, mivel a G1 nyelvtan S → B egységtermelést tartalmaz, eltávolítási hozama:

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

Távolítsa el az S1 → S egységprodukciót is, ennek eltávolítása a nyelvtanból a következő eredményt kapja:

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

3. lépés: Az S0 → aA | termelési szabályban Aa, S → aA | Aa, A → aBB és B → Aa, az a terminál létezik az RHS-en nem terminálokkal. Tehát az a terminált X-re cseréljük:

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

4. lépés: Az A → XBB előállítási szabályban az RHS kettőnél több szimbólumot tartalmaz, ami eltávolítja a nyelvtani hozamból:

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

Ezért az adott nyelvtanhoz ez a szükséges CNF.

húrfordítás c