Chomsky normálforma polinomidőben

Egy környezetfüggetlen nyelvtan (továbbiakban CF nyelvtan, vagy csak CFG) Chomsky alakú, ha kétféle szabály van benne:

• A → BC (egy változót cserélhetünk két változóra)
• A → a (egy változót cserélhetünk egy betűre)

Mármost ha csak ilyen szabályokat engednénk meg, akkor az üres szót (most legyen ennek jele ε) nem lehetne levezetni a kezdőszimbólum S-ből, mert nem tudna rövidülni a munkastringünk. Ezért kivételként megengedjük az S → ε szabályt, de csak akkor, ha S amúgy nem szerepel jobb oldalon sehol (ha szerepelne, akkor az megfektetene néhány elemző algoritmust, amik CF nyelvtanokra működnek).

Minden CF nyelvtant lehet Chomsky alakra hozni, ehhez négy alaplépés van:

1. Az ε jobboldalú szabályoktól megszabadulunk, ezt nevezzük ε-mentesítésnek.
2. Az A → B (egy változót egy változóra átíró) ún. láncszabályoktól is megszabadulunk, ezt hívjuk láncszabálymentesítésnek.
3. Ha van olyan jobb oldal, ami legalább három hosszú, azt több részbe daraboljuk, nevezhetjük ezt mondjuk darabolásnak.
4. Ha marad A → aB, Ba, aa alakú szabály, tehát ami ugyan kettő hosszú, de van benne terminális, akkor ahhoz a terminálishoz bevezetünk egy új változót, azt írjuk az ilyen jobboldalakba, és abból az új változóból csak ezt a terminálist lehessen levezetni. Legyen mondjuk a neve ennek nagybetűsítés :D

A legtöbb egyetemen a világon ezt konkrétan ebben a sorrendben is tanítják, hogy így kell csinálni

de ez egyszerűen plain wrong

mert exponenciálisan is nagyobb nyelvtant eredményezhet, teljesen feleslegesen, ahogy mindjárt látni is fogjuk.

Nézzük az átalakításokat egyenként.

ε-mentesítés.

• Először meghatározzuk egy sima fixpontiterációval, hogy kikből lehet egyáltalán ε-t levezetni, egy vagy több lépésben. Tehát egy N halmazba tesszük az ilyen szimbólumokat:
• inicializálás: azokat az A-kat tesszük N-be, akikre van A → ε szabály.
• iteráció: ha találunk olyan A változót, amire van olyan A → X1X2...Xk szabály, amiről az összes Xi már benne van N-ben, akkor tegyük bele A-t is N-be. (világos: ha minden Xi-t ki tudok nullázni, akkor az A-t is úgy, hogy előbb X1..Xk-ra átírom, aztán kinullázom az összes Xi-t)
• fixpontiterációt csinálunk, azaz addig toljuk az iterációs lépést, amíg a halmazunk már nem változik tovább.
• Ezek után pedig átalakítjuk a nyelvtant: az új nyelvtan szabálya úgy készülnek, hogy 
• ahányféleképpen el lehet hagyni nullázható (N-beli) változót jobb oldalról, annyiféleképp elhagyjuk,
• de persze A → ε szabályt nem veszünk fel (ami eredetileg is ilyen volt, vagy ha úgy kapnánk, hogy mindent elhagyunk).
• Ha ezt csináljuk, akkor még ellenőrizni kell, hogy S, a kezdőszimbólum nullázható-e. Ha az, akkor fel kell vegyünk egy új S0 kezdőszimbólumot, és S0 → S | ε szabályokat. (Emiatt az új kezdőszimbólumból egyrészt le tudunk vezetni üres szót is, másrészt mivel új, biztos nem volt jobb oldalon.) De még egyszer: ezt csak akkor, ha S N-beli, nullázható változó.

Nézzünk példát:

S → AB | AAaB | CBA

A → BB | aBBa | a

B → ε | aSB

C → aA | BC

Ekkor eredetileg N = { B }, mert van B → ε szabály.

Eztán iterációban találunk egy A → BB szabályt, aminek a jobb oldalát ki tudjuk nullázni (mind a két B benne van N-ben), tehát A-t is nullázhatjuk: N = { A, B }.

Eztán S → AB miatt, mert A és B is benne van N-ben, S is nullázható: N = { A, B, S }.

C nem kerül bele, mert aA-ban a, BC-ben pedig C nem nullázható. Tehát az N = { A, B, S } halmaz az összes nullázható változó halmaza.

Következő lépésben ahányféleképp lehet, elhagyunk N-beli elemeket a jobb oldalakról, figyelve arra, hogy ε ne maradjon:

S → AB | A | B lesz az S → AB-ből: elhagyhatjuk A-t is, B-t is, vagy egyiket se; mindkettőt azért nem, mert akkor nem maradna semmi;

S → AAaB-ből lesz S → AAaB | AaB | aB | AAa | Aa | a,

A → BB -ből A → BB | B,

és így tovább, a majdnem végeredmény:

S → AB | A | B | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | C

A → BB | B | aBBa | aBa | aa | a

B → aSB | aS | aB | a

C → aA | a | BC | C

utolsó lépésben ugye C nem nullázható, azért nem hagytuk el egyszer sem.

A végeredmény pedig mivel S is nullázható: ugyanez, plusz
S0 → S | ε

Láncszabálymentesítés.

• Először minden A változóra meghatározzuk azt a CA halmazt, amiben pontosan az összes olyan változó van, amiket A-ból láncszabályokkal el lehet érni. Nulla darab láncszabállyal is, tehát A mindig bekerül CA-ba. Ha ezt is fixpontiterációval csináljuk, akkor CA = { A } -val inicializálunk, aztán ha találunk olyan láncszabályt, aminek bal oldala CA-beli, jobb oldala meg nem, akkor betesszük a jobb oldalt is CA-ba.
• Egyébként ezt gráfosan is meg lehet csinálni: készítünk egy gráfot, csúcsai a változók, A-ból B-be akkor megy él, ha van A → B láncszabály, ekkor CA-ba pont az A-ból elérhető csúcsok kerülnek bele.
• Miután megvan az összes CA halmaz, az A változó új jobboldalai az összes CA-beli változó eredeti jobb oldalai lesznek, kivéve a láncszabályokat.

Folytatva az előző példát, CS = { S } inicializálás, van S → A és S → B szabály, sőt S → C is, ezért A, B és C is bekerülnek CS-be: CS = { S, A, B, C }.

CA = { A }, inicializálás, van A → B láncszabály, bekerül B, de se A-ból, se B-ből nem indul több láncszabály, ezért marad CA = { A, B }.

CB = { B }, nincs B-ből láncszabály, ez így marad.

CC = { C }, van ugyan C → C, de egyrészt minek, másrészt C már benne van CC-ben, így marad.

Akiről elfeledkeztem: CS0 = { S0, S, A, B, C }, először S0 került bele, majd S0 → S miatt S is, majd S → A | B | C miatt a másik három.

Hogy ezek a halmazok megvannak, pl. S új jobboldalai mindenki lesz, aki eredetileg akár S, akár A, B vagy C jobb oldalán szerepelt, kivéve a láncszabályokat, stb. eredmény:

S0 → ε | AB | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | BB | aBBa | aBa | aa | a | aSB | aS | aB | a | aA | a | BC

S → AB | AAaB | AaB | aB | AAa | Aa | a | CBA | CB | CA | BB | aBBa | aBa | aa | a | aSB | aS | aB | a | aA | a | BC

A → BB | aBBa | aBa | aa | a | aSB | aS | aB | a

B → aSB | aS | aB | a

C → aA | a | BC

Aki cizellálni akarja, persze kiszűrheti az ismétlődéseket például, S-nek és S0-nak "a" az legalább háromszor van a jobb oldalán, de kit zavar :D ez a vége a láncszabály-mentesítésnek,

Darabolás.

Itt mindössze annyi a dolgunk, hogy ha túl hosszú (értsd, legalább három hosszú) a jobb oldal, akkor az első betűjét megtartjuk, a maradék rész helyett pedig egy egészen új változót vezetünk be, amiből ezt a részt levezethetjük egy lépésben. Ha túl hosszú így is, akkor ezt tovább folytatjuk. Pl. a fenti S0 → AAaB szabályból lesz S0 → AX, X → AY, Y → aB, ahol X és Y teljesen új változók.

Mondjuk írásban én úgy szoktam ajánlani, hogy pl. egy AaB stringből egy [AaB] nevű változót készítsünk, akkor jobban követhető, hogy mi történik: S0 → A[AaB], [AaB] → A[aB], [aB] → aB szerintem jobban látszik, ha debugolni kell valamiért, hogy mi történt.

Nagybetűsítés.

Ahogy korábban is mondtam, ha mondjuk van egy C → aA szabályunk, ez azért nem Chomsky, mert az a-nak is változónak kéne lennie. Hogy az legyen, minden a betűhöz felveszünk egy egészen új Xa változót, egy Xa → a szabályt és a jobb oldalakban levő a-kat Xa-kra cseréljük. Lesz ebből pl. C → XaA, Xa → a.

Az eredeti nyelvtant tovább ütve az utolsó két lépéssel azt kapjuk, hogy

S0 → ε | AB | A[AaB] | A[aB] | XaB | A[Aa] | AXa | a | C[BA] | CB | CA | BB | Xa[BBa] | a[Ba] | XaXa | Xa[SB] | XaS | XaB | XaA | BC

S → AB | A[AaB] | A[aB] | [aB] | A[Aa] | AXa | a | C[BA] | CB | CA | BB | Xa[BBa] | Xa[Ba] | XaXa | Xa[SB] | XaS | XaB | XaA | BC

A → BB | Xa[BBa] | Xa[Ba] | XaXa | a | Xa[SB] | XaS | XaB

B → Xa[SB] | XaS | XaB | a

C → XaA | a | BC

[AaB] → A[aB]

[aB] → XaB

[Aa] → AXa

[BA] → BA

[BBa] → B[Ba]

[Ba] → BXa

[SB] → SB

Xa → a

meseszép. (nem.) (de legalább Chomsky alakú.)

Elemezve a méretet, amit kapunk, azt látjuk, hogy az ε-mentesítésnél durván elszállhat a dolog, pl. ha a nyelvtan

S → X1X2...Xn

X1 → a1 | ε

X2 → a2 | ε

...

Xn → an | ε

akkor minden Xi és S is nullázható lesz az ε-mentesítéskor, ezért az S új jobboldalán $2^{n-1}$ különböző string születik és ekkora lesz a Chomsky-alak is.

that's plain wrong.

Nyilván az igaz, hogy az ε-mentesítés behozhat láncszabályokat, tehát előbb kell ε-mentesíteni, és csak aztán láncszabályozni. A nagybetűsítést tkp bármikor megcsinálhatjuk, az nem növeli lényegesen a nyelvtan méretét. A láncszabály-mentesítés, mivel csak jobboldalakat másolunk, nem fog behozni se hosszú jobboldalt, se ε-szabályt, ha már eleve nem volt. A darabolás se hoz be se láncszabályt, se ε-szabályt, az is igaz. De ha a költségeket nézzük:

• ε-mentesítés: $k$ hosszú szabályból $O(2^k)$ hosszú szabály születhet;
• láncszabály-mentesítés: négyzetesen lehet nagyobb a nyelvtan mérete tőle;
• darabolás: konstansszor lesz nagyobb a nyelvtan;
• nagybetűsítés: elhanyagolható, kisbetűnként egy új szabály.

Ezek miatt ha a sorrendet arra vesszük, hogy

1. darabolás
2. ε-mentesítés
3. láncszabály-mentesítés
4. nagybetűsítés

akkor az egész trafó max négyzetes méretű nyelvtant ad

mert a darabolás után minden jobb oldal max kettő hosszú, ezt a nullázással már csak háromszor akkorává tudjuk duzzasztani (eddig tehát hatszor akkora a nyelvtanunk, mint volt, tops), erre jön a négyzetes láncszabály-mentesítés, majd a nagybetűsítés, az egész csak négyzetes marad.

Ha ebben a sorrendben megyünk végig az eredeti inputon:

S → AB | AAaB | CBA

A → BB | aBBa | a

B → ε | aSB

C → aA | BC

darabolás:

S → AB | A[AaB] | C[BA]

[AaB] → A[aB]

[aB] → aB

[BA] → BA

A → BB | a[BBa] | a

[BBa] → B[Ba]

[Ba] → Ba

B → ε | a[SB]

[SB] → SB

C → aA | BC

ε-mentesítés: nullázni lehet {B, A, S, [BA], [SB]} változókat, ezeket elhagyogatva:

S0 → S | ε

S → AB | A | B | A[AaB] | [AaB] | C[BA] | C

[AaB] → A[aB] | [aB]

[aB] → aB

[BA] → BA | B | A

A → BB | B | a[BBa] | a

[BBa] → B[Ba] | [Ba]

[Ba] → Ba

B → a[SB]

[SB] → SB | S | B

C → aA | BC | C

láncszabály-mentesítés: S0-ból {S0, S, A, B, C } érhető el láncszabályokkal, S-ből {S, A, B, C}, [AaB]-ből {[AaB], [aB] }, [aB]-ből csak önmaga, [BA]-ből {[BA], B, A}, A-ból {A, B}, [BBa]-ból és [Ba]-ból csak önmaguk, B-ből és C-ből is, [SB]-ből pedig {[SB], S, B, A, C}. Akkor ez rögtön nagybetűsítve is:

S0 → ε | AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

S → AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

[AaB] → A[aB] | XaB

[aB] → XaB

[BA] → BA | BB | Xa[BBa] | a | Xa[SB]

A → BB | Xa[BBa] | a | Xa[SB]

[BBa] → B[Ba]

[Ba] → Ba

B → Xa[SB]

[SB] → SB | AB | A[AaB] | [AaB] | C[BA] | BB | Xa[BBa] | a | Xa[SB] | XaA | BC

C → XaA | BC

Xa → a

négyzetes az egész, frankó.

csakhogy.

Nem tudjuk (és engem érdekel), hogy a láncszabály-mentesítéshez (az a bottleneck, minden más lineáris a történetben) tényleg kell-e az a négyzetes algoritmus, vagy van ennél jobb is. Ami tudomásom szerint ismert, az az, hogy legalábbis $\Omega(n^{3/2})$ költsége biztos van a láncszabály-mentesítésnek, de hogy ez elég lenne, vagy négyzetes kell mindig, nem tudjuk.