上下文有關語言

上下文有關語言是著名語言學家Noam Chomsky定義了四類文法和四種形式語言類。

文法分類（A hierarchy of Grammars）著名語言學家Noam Chomsky定義了四類文法和四種形式語言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在於對產生式施加不同的限制，分別是：
* 0型文法(短語結構文法)(phrase structure grammars)：
設G=(，，，)，如果它的每個產生式是這樣一種結構： (∪)　且至少含有一個非終結符，而(∪)，則G是一個0型文法。
* 1型文法（上下文有關文法）(context-sensitive grammars)：
設G=(，，，)為一文法，若中的每一個產生式均滿足|，僅僅　除外，則文法G是1型或上下文有關的。
* 2型文法（上下文無關文法）(context-free grammars)：
設G=(，，，)，若P中的每一個產生式滿足：是一非終結符，(∪)　則此文法稱為2型的或上下文無關的。
* 3型文法（正規文法）(regular grammars)：
設G=(，，，)，若中的每一個產生式的形式都是A→aB或A→a，其中A和B都是非終結符，a是終結符，則G是3型文法或正規文法。
0型文法產生的語言稱為0型語言。
1型文法產生的語言稱為1型語言，也稱作上下文有關語言。
2型文法產生的語言稱為2型語言，也稱作上下文無關語言。
3型文法產生的語言稱為3型語言，也稱作正規語言。