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

From Wikipedia, the free encyclopedia

Remove ads

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

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

Remove ads

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

Формална граматика је контекстно-сензитивна ако су сва правила из скупа облика

где (то јест, је један незавршни симбол), (то јест, и су ниске незавршних и завршних симбола) (то јест, је непразна ниска незавршних и завршних симбола).

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

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

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

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

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

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

Remove ads

Примери

Ова граматика генерише канонски не-контекстно-слободни језик :

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


Компликованије граматике могу да се користе за парсирање , и других језика са још више слова:

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

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

Remove ads

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

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

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

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

Проблем празности за контекстно-сензитивне граматике (да ли за дату контекстно сензитивну граматику , важи  ?) је неодлучив.

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

Remove ads

Види још

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads