Контекст-сензитивни језик
У теоријском рачунарству, контекст-сензитиван језик је формални језик који може да се дефинише контекст-сензитивном граматиком. То је једна од четири типа граматика у Хијерархији Чомског. Од њих четири, ова граматика се најређе користи, и у теорији и у пракси.
Рачунска својства
[уреди | уреди извор]Рачунски, контекстно-сензитивни језици су еквивалентни са линерно ограниченим недетерминистичким Тјуринговим машинама, које се називају још и линеарно ограниченим аутоматима. То је недетерминистичка Тјурингова машина са траком која има само 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.
- Immerman, Neil (1988). „Nondeterministic space is closed under complementation” (PDF). SIAM J. Comput. 17 (5): 935—938. doi:10.1137/0217058.