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

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

Рачунска својства

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

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

Примери

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

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

Својства контекстно-сензитивних језика

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

Види још

• Линеарно ограничен аутомат
• Хијерархија Чомског
• Несажимајућа граматика
• Индексирани језици – строги подскуп контекстно-сензитивних језика

Литература

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

• Immerman, Neil (1988). „Nondeterministic space is closed under complementation” (PDF). SIAM J. Comput. 17 (5): 935—938. doi:10.1137/0217058.