Kontextový jazyk
kontextový jazyk je formální jazyk to může být definováno kontextovou gramatikou. To je jeden z čtyř druhů gramatik v Chomsky hierarchii. Čtyři, toto je nejméně často použitý, v jak teorii tak praxi.Computationally kontextové jazyky jsou rovnocenné s lineárním ohraničeným non-deterministický Turing stroje. To je non-deterministický Turing stroj s páskou jediný kn buňky, kde n je velikost vstupu a k je konstanta spojená se strojem. Toto znamená, že každý formální jazyk, který může být se rozhodl takový stroj je kontextový jazyk a každý kontextový jazyk může být rozhodnut takový stroj.
Tento soubor jazyků je také známý jak NLIN-prostor, protože oni mohou být přijímáni používat lineární prostor na non-deterministický Turing stroj. Třída Lin-prostor je definován stejný, kromě používat deterministický Turing stroj. Jasně Lin-prostor je podmnožina NLIN-prostor, ale to není známé zda Lin-prostor=NLIN-prostor. To je široce tušil, že oni nejsou se rovnat.
Každý kontext-volný jazyk je kontextový.
Příklad kontextového jazyka, který není kontext-volný je L = { n : n je prvočíslo }. Nejsnadnější způsob, jak ukazovat toto používá lineární ohraničený Turing stroj.
Viz též: Chomsky hierarchie