文法分類（A hierarchy of Grammars）著名語言學家Noam Chomsky定義了四類文法和四種形式語言類，文法的四種類型分別是0型、1型、2型和3型。
基本介紹
- 中文名：上下文有關語言
- 外文名：A hierarchy of Grammars
- 提出者：Noam Chomsky
- 類型：0型、1型、2型和3型
簡介,文法內容,計算性質,上下文有關語言的性質,
簡介
文法內容
幾類文法的差別在於對產生式施加不同的限制，分別是：
* 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型語言，也稱作正規語言。
計算性質
上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有kn個單元的非確定圖靈機，這裡的n是輸入的大小而k是與這個機器關聯的常數。這意味著可以被這種機器判定的所有形式語言都是上下文有關語言，而所有上下文有關語言都可以被這種機器判定。
這種語言的集合也叫做NLIN-SPACE，因為它們可以在非確定圖靈機上使用線性空間來接受。類LIN-SPACE定義相同，除了使用確定圖靈機之外。。明顯的LIN-SPACE是NLIN-SPACE的子集，但不知道是否LIN-SPACE=NLIN-SPACE。普遍猜測它們是不相等的。
上下文有關語言的性質
- 兩個上下文有關語言的並集、交集和串接也是上下文有關的。
- 上下文有關語言的補集自身是上下文有關的。
- 所有上下文無關語言都是上下文有關的。
- 一個字元串在由任意上下文有關文法，或任何確定上下文有關文法所定義的語言中的成員關係是PSPACE-完全問題。
