Контекст-сензитивни језик

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

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

Рачунска својства[уреди]

Рачунски, контекстно-сензитивни језици су еквивалентни са линерно ограниченим недетерминистичким Тјуринговим машинама, које се називају још и линеарно ограниченим аутоматима. То је недетерминистичка Тјурингова машина са траком која има само kn ћелија, где је n величина улаза, а k је константа везана за машину. Ово значи да је сваки формални језиик који може да буде одлучен таквом машином контекстно-сензитиван, и да је сваки контекстно-сензитиван језик одлучив таквом машином.

Овај скуп језика је такође познат као NLIN-SPACE, јер може да их препозна недетерминистичка Тјурингова машина користећи линеарни простор. Класа LIN-SPACE се дефинише на исти начин, осим што се користи детерминистичка Тјурингова машина. Јасно, LIN-SPACE је подскуп од NLIN-SPACE, али није познато да ли је LIN-SPACE=NLIN-SPACE. Распрострањено је мишљење да ове две класе нису једнаке.

Примери[уреди]

Пример контекст-сензитивног језика који није контекст-слободан је L = { ap : p је прост број}. За L се може показати да је контекст-сензитиван конструисањем линеарно ограниченог аутомата који прихвата L. Лако се може показати да овај језик није ни регуларан, нити контекстно-слободан примењивањем одговарајуће пампинг леме за обе класе језика на L.

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

Својства контекстно-сензитивних језика[уреди]

  • Унија, пресек и конкатенација два контекст-сензитивна језика је контекст-сензитивна.
  • Комплемент контекстно-сензитивног језика је контекстно-сензитиван.
  • Сваки контекстно-слободан језик је контекстно-сензитиван.
  • Припадност неке ниске језику дефинисаном произвољном контекстно-сензитивном граматиком, или произвољном детерминистичком контекстно-сензитивном граматиком, је PSPACE-комплетан проблем.

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

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

  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.