У теоријском рачунарству, контекст-сензитиван језик је формални језик који може да се дефинише контекст-сензитивном граматиком. То је једна од четири типа граматика у Хијерархији Чомског. Од њих четири, ова граматика се најређе користи, и у теорији и у пракси.
Рачунска својства Рачунски, контекстно-сензитивни језици су еквивалентни са линерно ограниченим недетерминистичким Тјуринговим машинама, које се називају још и линеарно ограниченим аутоматима. То је недетерминистичка Тјурингова машина са траком која има само -{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.}-
Категорија:Формални језици