上下文有關語言

在理論計算機科學中，上下文有關語言是可被上下文有關文法定義的形式語言。它是喬姆斯基層級中的四類文法之一。當然它在理論和實踐中都是最少使用的。

幾類文法的差別在於對產生式施加不同的限制，分別是：

* 0型文法(短語結構文法)(phrase structure grammars)：

設G =（VN，VT，P，S），如果它的每個產生式是這樣一種結構：α∈(VN∪VT)*　且至少含有一個非終結符，而β∈(VN∪VT)*，則G是一個0型文法。

* 1型文法（上下文有關文法）(context-sensitive grammars)：

設G =（VN，VT，P，S）為一文法，若中的每一個產生式均滿足|β|>=|α|，僅僅α→ε除外，則文法G是1型或上下文有關的。

* 2型文法（上下文無關文法）(context-free grammars)：

設G =（VN，VT，P，S），若P中的每一個產生式滿足：α是非終結符，β∈(VN∪VT)*，同時又滿足1型文法的條件，則此文法稱為2型的或上下文無關的。

* 3型文法（正規文法）(regular grammars)：

設G =（VN，VT，P，S），若中的每一個產生式的形式都是A→aB或A→a，其中A和B都是非終結符，a是終結符，則G是3型文法或正規文法。

0型文法產生的語言稱為0型語言。

1型文法產生的語言稱為1型語言，也稱作上下文有關語言。

2型文法產生的語言稱為2型語言，也稱作上下文無關語言。

3型文法產生的語言稱為3型語言，也稱作正規語言。 ^[1] 

上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有kn個單元的非確定圖靈機，這裏的n是輸入的大小而k是與這個機器關聯的常數。這意味着可以被這種機器判定的所有形式語言都是上下文有關語言，而所有上下文有關語言都可以被這種機器判定。

這種語言的集合也叫做NLIN-SPACE，因為它們可以在非確定圖靈機上使用線性空間來接受。類LIN-SPACE定義相同，除了使用確定圖靈機之外。。明顯的LIN-SPACE是NLIN-SPACE的子集，但不知道是否LIN-SPACE=NLIN-SPACE。普遍猜測它們是不相等的。 ^[1]