Контекстно-сензитивна граматика

Контекстно-сензитивна граматика је формална граматика код које лева и десна страна сваког правила извођења може да буде окружена контекстом завршних и незавршних симбола. Контекстно-сензитивне граматике су општије од контекстно слободних граматика али су још увек довољно уређене да могу да их парсирају линеарно ограничени аутомати.

Појам контекстно-сензитивне граматике је увео Ноам Чомски током педесетих година двадесетог века као начин за описивање синтаксе природних језика где је заиста чест случај да реч може али и не мора да буде прихватљива на одређеном месту у зависности од контекста. Формални језик који може да буде описан контекстно-сензитивном граматиком се назива контекстно-сензитивним језиком.

Формална дефиниција

Формална граматика G = (N, Σ, P, S) је контекстно-сензитивна ако су сва правила из скупа P облика

αAβ → αγβ

где A ∈ N (то јест, A је један незавршни симбол), α, β ∈ (N U Σ)* (то јест, α и β су ниске незавршних и завршних симбола) а γ ∈ (N U Σ)⁺ (то јест, γ је непразна ниска незавршних и завршних симбола).

Неке дефиниције додају и да за свако правило извођења облика u → v контекстно-сензитивне граматике мора да важи u|≤|v|. Овде u| и v| означавају дужине ниски u и v.

Осим тога, дозвољено је и правило облика

S → λ под условом да се S не појављује на десној страни ниједног правила.

Овде λ представља празну ниску. Додавање празне ниске омогућава тврдњу да су контекстно-сензитивни језици прави надскуп контекстно-слободних језика, уместо слабије тврдњее да су све контекстно-слободне граматике без →λ извођења уједно и контекстно-сензитивне граматике.

Име контекстно-сензитивна се објашњава тиме што α и β формирају контекст за A чиме одређују да ли A може да се преслика у γ или не. Ово је разлика у односу на контекстно-слободне граматике код којих контекст у ком се незавршни симбол налази не узима у разматрање.

Ако се могућност додавања празне ниске у језик дода у скуп ниски препознатих од стране неконтрактивних граматика (које никада не могу да укључе празну ниску) онда су језици у ове две дефиниције идентични.

Примери

Ова граматика генерише канонски не-контекстно-слободни језик ${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 1\}}$:

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

Ток извођења за aaa bbb ccc је:

${\displaystyle S}$

${\displaystyle \Rightarrow _{1}aSBC}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компликованије граматике могу да се користе за парсирање ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}}$, и других језика са још више слова:

S → abcd

S → aXbcd

Xb → bX

Xc → bYc

Yc → cY

Yd → Rcdd

cR → Rc

bR → Rb

aa

(Ова граматика у ствари није контекстно-сензитивна због присуства правила извођења облика Xb → bX. Међутим, постоји контекстно-сензитивна граматикак за овај језик.)

Ток извођења за aaa bbb ccc ddd је:

S

aXbcd

abXcd

abbYcd

abbcYd

abbcRcdd

abbRccdd

abRbccdd

aRbbccdd

aaXbbccdd

aabXbccdd

aabbXccdd

aabbbYccdd

aabbbcYcdd

aabbbccYdd

aabbbccRcddd

aabbbcRccddd

aabbbRcccddd

aabbRbcccddd

aabRbbcccddd

aaRbbbcccddd

aaabbbcccddd

Нормалне форме

Свака контекстно-осетљива граматиак која не генерише празну ниску може да се трансформише у еквивалентну граматику у нормалној форми Куроде. Овде еквивалентну значи да две граматике генеришу исти језик. Нормална форма у општем случају не мора да буде контекстно-сензитивна, али мора да буде неконтрактивна граматика.

Рачунска својства и употребе

Проблем одлучивања који поставља питање да ли одређена ниска s припада језику одређене контекстно-сензитивне граматике G, је PSPACE-комплетан. Постоје и неке контекстно-сензитивне граматике за које је проблем препознавања фиксне граматике PSPACE-комплетан.

Проблем празности за контекстно-сензитивне граматике (да ли за дату контекстно сензитивну граматику G, важи ${\displaystyle L(G)=\emptyset }$ ?) је неодлучив.

Показано је да скоро сви природни језици могу у општем случају да буду описани контекстно-сензитивним граматикама, али цела класа контекснто-сензитивних граматика изгледа да је много шира од скупа природних језика. Осим тога, како је поменути проблем одлучивања за контекстно-сензитивне граматике PSPACE-комплетан, то их чини у потпуности неупотребљивим за практичне употребе, јер би полиномијални алгоритам за PSPACE-комплетан проблем имплицирао П=НП. Текућа истраживања у рачунарској лингвистици су усмерена на формулисање других класа језика који су благо контекстно-сензитивни, чији би проблеми одлучивања били изводљиви. Језици генерисани овим формализмима су прави подскупови контекстно-сензитивних и прави надскупови контекстно-слободних језика.

Види још

• Хијерархија Чомског

Литература

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