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

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

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

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

Формална граматика -{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}- може да се преслика у -{γ}- или не. Ово је разлика у односу на контекстно-слободне граматике код којих контекст у ком се незавршни симбол налази не узима у разматрање.

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

Примери

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

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

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

$S$

${\Rightarrow }_{1}aSBC$

${\Rightarrow }_{1}a𝒂𝑺𝑩𝑪BC$

${\Rightarrow }_{2}aa𝒂𝑩𝑪BCBC$

${\Rightarrow }_{3}aaaB𝑯𝑩CBC$

${\Rightarrow }_{4}aaaB𝑯𝑪CBC$

${\Rightarrow }_{5}aaaB𝑩𝑪CBC$

${\Rightarrow }_{3}aaaBBC𝑯𝑩C$

${\Rightarrow }_{4}aaaBBC𝑯𝑪C$

${\Rightarrow }_{5}aaaBBC𝑩𝑪C$

${\Rightarrow }_{3}aaaBB𝑯𝑩CC$

${\Rightarrow }_{4}aaaBB𝑯𝑪CC$

${\Rightarrow }_{5}aaaBB𝑩𝑪CC$

${\Rightarrow }_{6}aa𝒂𝒃BBCCC$

${\Rightarrow }_{7}aaa𝒃𝒃BCCC$

${\Rightarrow }_{7}aaab𝒃𝒃CCC$

${\Rightarrow }_{8}aaabb𝒃𝒄CC$

${\Rightarrow }_{9}aaabbb𝒄𝒄C$

${\Rightarrow }_{9}aaabbbc𝒄𝒄$

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

-{S → abcd}-

-{S → aXbcd}-

-{Xb → bX}-

-{Xc → bYc}-

-{Yc → cY}-

-{Yd → Rcdd}-

-{cR → Rc}-

-{bR → Rb}-

-{aR → aaX | 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}-, важи $L(G)=\mathrm{\varnothing }$ ?) је неодлучив.

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

Види још

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

Литература

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