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