可計算枚舉語言被命名為0-型語言，上下文相關語言被命名為1-型語言，上下文無關語言被命名為2-型語言，正則語言被命名為3-型語言。低型語言不是高型的，默認情況下，每個高型的語言都是低型的，這個被稱為喬姆斯基分層。
基本介紹
- 中文名：喬姆斯基分層
- 外文名：Chomsky hierarchy
- 層次：1-型、2-型、3-型、0-型
- 定義：低級語言不是高型
- 系統：計算機
- 學科：計算機技術
內容簡介,喬姆斯基形式文法,短語結構文法,正則文法,
內容簡介
存在正則語言的一個擴展。在正則語言裡，一個非終結符號可以像串最右端符號那樣出現任一生成式的右邊。這種語法也叫作右線性語法(right linear grammars)。當語法中每個生成式最多有一個非終結符在它右邊，並且非終結符像最左端符號那樣出現左邊時，語法叫作左線性語法(1eft linear grammar)。線上性語法中，每個生成式在右邊之多有一個非終結符，在位置上則無任何限制。
可以證明，線性語言，即由線性語法生成的語言，形成了上下文無關語言的一個子集。
很顯然，每個正則語言都是線性的。線性語言類與確定性上下文無關語言不同。這些結果總結起來叫作喬姆斯基層次結構(Chomsky’s Hierarchy)。它規定：
每一個正則語言都是線性的。
每一個正則語言都是確定性上下文無關的。
每一個線性語言都是上下文無關的。
每一個確定性上下文無關語言都是上下文無關的。
每一個上下文無關語言都是上下文相關的。
每一個上下文相關語言都是可判定的。
每一個可判定語言都是可計算枚舉的。
此外，先前說明的語言類之間的包含關係是固有的。其意味著：
存在可計算枚舉語言是不可判定的。
存在可判定語言是非上下文相關的。
存在上下文相關語言是非上下文無關的。
存在上下文無關語言不是確定性上下文無關的。
存在上下文無關語言不是線性的。
存在確定性上下文無關語言不是正則的。
存線上性語言不是正則的。
存在確定性上下文無關語言不是線性的。
存線上性語言不是確定性上下文無關的。
線性有界自動機是非確定性圖靈機帶上線性空間的約束。相似的約束在確定性圖靈機上隨之產生了所謂的確定性線性有界自動機(deterministic linear bounded automata)。還未知的是，確定性線性有界自動機接受語言是否構成那些(非確定性)線性有界自動機接受語言的子集。
設定一個字母表三。設RE，REC，CS，CF，LIN，DCF，REG各自分別表示語言類包括三上所有可計算枚舉(遞歸可枚舉的)、可判定(遞歸)、上下文相關、上下文無關、線性、確定性上下文無關，和正則語言。喬姆斯基層次結構可以寫成更進一步地，正則語言那些能被有限自動機接受的；上下文無關語言是那些被疊加自動機接受的；上下文相關語言是那些被線性有界自動機接受的；可計算枚舉語言是那些被圖靈機接受的。
由於這個層次結構，可計算枚舉語言被命名為0-型語言，上下文相關語言被命名為1-型語言，上下文無關語言被命名為2-型語言，正則語言被命名為3-型語言。低型語言不是高型的，默認情況下，每個高型的語言都是低型的。這個被稱為喬姆斯基層次結構，而上述闡明的結果構成了擴展的喬姆斯基層次結構。
喬姆斯基形式文法
在計算機科學中，形式語言是某個字母表上一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。最常見的文法的分類系統是喬姆斯基(Chomsky N)於1950年發展的喬姆斯基譜系，這個分類譜系把所有的文法分成四種類型：短語結構文法、上下文有關文法、上下文無關文法和正規文法。任何語言都可以由無限制文法來表達，餘下的三類文法對應的語言類分別是遞歸可枚舉語言、上下文無關語言和正規語言。依照排列次序，這四種文法類型依次擁有越來越嚴格的產生式規則，所能表達的語言也越來越少。儘管表達能力比短語結構文法和上下文相關文法要弱，但由於能高效率的實現，上下文無關文法和正規文法成為四類文法中最重要的兩種文法類型。
短語結構文法
短語結構文法是一種非受限文法，也稱為0型文法，是形式語言理論中的一種重要文法。
正則文法
正則文法來源於20世紀50年代中期喬姆斯基對自然語言的研究，是喬姆斯基短語結構文法分層里的3型文法。正則文法類是上下文無關(2型)文法類的真子類，已套用於電腦程式語言編譯器的設計、詞法分析(文本處理中描述觸發過程動作的文本模式、檔案類型和掃描器、文本工具的標準基礎)、開關電路設計、句法模式識別等，是計算機和信息科學、工程、物理、化學、生物、醫學、套用數學不可忽視的論題。
正則文法有多種等價的定義，可以用“左線性文法”或者“右線性文法”來等價地定義正則文法。“左線性文法”要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號。“右線性文法”要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個終結符號後隨一個非終結符號。
