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

Из Википедије, слободне енциклопедије

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

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

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

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

αAβ → αγβ

где AN (то јест, 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 \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

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

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}


Компликованије граматике могу да се користе за парсирање  \{ 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
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)=\emptyset ?) је неодлучив.

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

Види још[уреди]

Литература[уреди]

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


Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.