Kontekstno-senzitivna gramatika

Kontekstno-senzitivna gramatika je formalna gramatika kod koje leva i desna strana svakog pravila izvođenja može da bude okružena kontekstom završnih i nezavršnih simbola. Kontekstno-senzitivne gramatike su opštije od kontekstno slobodnih gramatika ali su još uvek dovoljno uređene da mogu da ih parsiraju linearno ograničeni automati.

Pojam kontekstno-senzitivne gramatike je uveo Noam Čomski tokom pedesetih godina dvadesetog veka kao način za opisivanje sintakse prirodnih jezika gde je zaista čest slučaj da reč može ali i ne mora da bude prihvatljiva na određenom mestu u zavisnosti od konteksta. Formalni jezik koji može da bude opisan kontekstno-senzitivnom gramatikom se naziva kontekstno-senzitivnim jezikom.

Formalna definicija

Formalna gramatika G = (N, Σ, P, S) je kontekstno-senzitivna ako su sva pravila iz skupa P oblika

αAβ → αγβ

gde A ∈ N (to jest, A je jedan nezavršni simbol), α, β ∈ (N U Σ)* (to jest, α i β su niske nezavršnih i završnih simbola) а γ ∈ (N U Σ)⁺ (to jest, γ je neprazna niska nezavršnih i završnih simbola).

Neke definicije dodaju i da za svako pravilo izvođenja oblika u → v kontekstno-senzitivne gramatike mora da važi u|≤|v|. Ovde u| i v| označavaju dužine niski u i v.

Osim toga, dozvoljeno je i pravilo oblika

S → λ pod uslovom da se S ne pojavljuje na desnoj strani nijednog pravila.

Ovde λ predstavlja praznu nisku. Dodavanje prazne niske omogućava tvrdnju da su kontekstno-senzitivni jezici pravi nadskup kontekstno-slobodnih jezika, umesto slabije tvrdnjee da su sve kontekstno-slobodne gramatike bez →λ izvođenja ujedno i kontekstno-senzitivne gramatike.

Ime kontekstno-senzitivna se objašnjava time što α i β formiraju kontekst za A čime određuju da li A može da se preslika u γ ili ne. Ovo je razlika u odnosu na kontekstno-slobodne gramatike kod kojih kontekst u kom se nezavršni simbol nalazi ne uzima u razmatranje.

Ako se mogućnost dodavanja prazne niske u jezik doda u skup niski prepoznatih od strane nekontraktivnih gramatika (koje nikada ne mogu da uključe praznu nisku) onda su jezici u ove dve definicije identični.

Primeri

Ova gramatika generiše kanonski ne-kontekstno-slobodni jezik $\{a^{n}b^{n}c^{n}:n\geq 1\}$:

1. $S\rightarrow aSBC$
2. $S\rightarrow aBC$
3. $CB\rightarrow HB$
4. $HB\rightarrow HC$
5. $HC\rightarrow BC$
6. $aB\rightarrow ab$
7. $bB\rightarrow bb$
8. $bC\rightarrow bc$
9. $cC\rightarrow cc$

Tok izvođenja za aaa bbb ccc je:

$S$

$\Rightarrow _{1}aSBC$

$\Rightarrow _{1}a{\boldsymbol {aSBC}}BC$

$\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC$

$\Rightarrow _{3}aaaB{\boldsymbol {HB}}CBC$

$\Rightarrow _{4}aaaB{\boldsymbol {HC}}CBC$

$\Rightarrow _{5}aaaB{\boldsymbol {BC}}CBC$

$\Rightarrow _{3}aaaBBC{\boldsymbol {HB}}C$

$\Rightarrow _{4}aaaBBC{\boldsymbol {HC}}C$

$\Rightarrow _{5}aaaBBC{\boldsymbol {BC}}C$

$\Rightarrow _{3}aaaBB{\boldsymbol {HB}}CC$

$\Rightarrow _{4}aaaBB{\boldsymbol {HC}}CC$

$\Rightarrow _{5}aaaBB{\boldsymbol {BC}}CC$

$\Rightarrow _{6}aa{\boldsymbol {ab}}BBCCC$

$\Rightarrow _{7}aaa{\boldsymbol {bb}}BCCC$

$\Rightarrow _{7}aaab{\boldsymbol {bb}}CCC$

$\Rightarrow _{8}aaabb{\boldsymbol {bc}}CC$

$\Rightarrow _{9}aaabbb{\boldsymbol {cc}}C$

$\Rightarrow _{9}aaabbbc{\boldsymbol {cc}}$

Komplikovanije gramatike mogu da se koriste za parsiranje $\{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}$, i drugih jezika sa još više slova:

S → abcd

S → aXbcd

Xb → bX

Xc → bYc

Yc → cY

Yd → Rcdd

cR → Rc

bR → Rb

aa

(Ova gramatika u stvari nije kontekstno-senzitivna zbog prisustva pravila izvođenja oblika Xb → bX. Međutim, postoji kontekstno-senzitivna gramatikak za ovaj jezik.)

Tok izvođenja za aaa bbb ccc ddd je:

S

aXbcd

abXcd

abbYcd

abbcYd

abbcRcdd

abbRccdd

abRbccdd

aRbbccdd

aaXbbccdd

aabXbccdd

aabbXccdd

aabbbYccdd

aabbbcYcdd

aabbbccYdd

aabbbccRcddd

aabbbcRccddd

aabbbRcccddd

aabbRbcccddd

aabRbbcccddd

aaRbbbcccddd

aaabbbcccddd

Normalne forme

Svaka kontekstno-osetljiva gramatiak koja ne generiše praznu nisku može da se transformiše u ekvivalentnu gramatiku u normalnoj formi Kurode. Ovde ekvivalentnu znači da dve gramatike generišu isti jezik. Normalna forma u opštem slučaju ne mora da bude kontekstno-senzitivna, ali mora da bude nekontraktivna gramatika.

Računska svojstva i upotrebe

Problem odlučivanja koji postavlja pitanje da li određena niska s pripada jeziku određene kontekstno-senzitivne gramatike G, je PSPACE-kompletan. Postoje i neke kontekstno-senzitivne gramatike za koje je problem prepoznavanja fiksne gramatike PSPACE-kompletan.

Problem praznosti za kontekstno-senzitivne gramatike (da li za datu kontekstno senzitivnu gramatiku G, važi $L(G)=\emptyset$ ?) je neodlučiv.

Pokazano je da skoro svi prirodni jezici mogu u opštem slučaju da budu opisani kontekstno-senzitivnim gramatikama, ali cela klasa konteksnto-senzitivnih gramatika izgleda da je mnogo šira od skupa prirodnih jezika. Osim toga, kako je pomenuti problem odlučivanja za kontekstno-senzitivne gramatike PSPACE-kompletan, to ih čini u potpunosti neupotrebljivim za praktične upotrebe, jer bi polinomijalni algoritam za PSPACE-kompletan problem implicirao P=NP. Tekuća istraživanja u računarskoj lingvistici su usmerena na formulisanje drugih klasa jezika koji su blago kontekstno-senzitivni, čiji bi problemi odlučivanja bili izvodljivi. Jezici generisani ovim formalizmima su pravi podskupovi kontekstno-senzitivnih i pravi nadskupovi kontekstno-slobodnih jezika.

Vidi još

• Hijerarhija Čomskog

Literatura

• Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)