喬姆斯基文法

喬姆斯基文法，也稱喬姆斯基體系，是計算機科學中刻畫形式文法表達能力的一個分類譜系，是由諾姆·喬姆斯基於1956年提出的。它包括四個層次：

基本介紹

• 中文名：喬姆斯基文法
• 外文名：Chomsky hierarchy
• 別稱：喬姆斯基體系

諾姆·喬姆斯基

艾弗拉姆·諾姆·喬姆斯基（英語：Avram Noam Chomsky，1928年12月7日－），或譯作“荷姆斯基”，美國哲學家、語言學家、認知學家、邏輯學家、政治評論家。喬姆斯基是麻省理工學院語言學的榮譽退休教授，他的生成語法被認為是20世紀理論語言學研究上的重要貢獻。他對伯爾赫斯·弗雷德里克·斯金納所著《口語行為》的評論，也有助於發動心理學的認知革命，挑戰1950年代研究人類行為和語言方式中占主導地位的行為主義。他所採用以自然為本來研究語言的方法也大大地影響了語言和心智的哲學研究。他的另一大成就是建立了喬姆斯基層級：根據文法生成力不同而對形式語言做的分類。喬姆斯基還因他對政治的熱忱而著名，尤其是他對美國和其它國家政府的批評。從1960年評論越南戰爭以來，他的媒體和政治評論便越來越著名。一般認為他是活躍在美國政壇左派的主要知識分子。喬姆斯基把自己歸為自由意志社會主義者，並且是無政府工團主義的同情者。據藝術和人文引文索引說，在1980年到1992年，喬姆斯基是被文獻引用數最多的健在學者，並是有史以來被引用數第八多的學者。

自動機理論

在理論計算機科學中，自動機理論是對抽象機和它們能解決的問題的研究。自動機理論密切關聯於形式語言理論，因為自動機經常按它們所能識別的形式語言類來分類。

自動機是有限狀態機（FSM）的數學模型。FSM是給定符號輸入，依據（可表達為一個表格的）轉移函式“跳轉”過一系列狀態的一種機器。在常見的FSM的“米利型有限狀態機”（Mealy）變體中，這個轉移函式告訴自動機給定當前狀態和當前字元的時候下一個狀態是什麼。

逐個讀取輸入中的符號，直到被完全耗盡(把它當作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。一旦輸入被耗盡，自動機被稱為“停止”了。

依賴自動機停止時的狀態，稱呼這個自動機要么是“接受”要么“拒絕”這個輸入。如果停止於“接受狀態”，則自動機“接受”了這個字。在另一方面，如果它停止於“拒絕狀態”，則這個字被“拒絕”。自動機接受的所有字的集合被稱為“這個自動機接受的語言”。

但要注意，自動機一般不必須有有限數目甚至可數個狀態。比如，量子有限自動機有不可數無限個狀態，因為所有可能狀態的集合是在復投影空間中所有點的集合。所以，量子有限自動機和有限狀態機一樣，都是更一般想法拓撲自動機的特殊情況，它的狀態的集合是拓撲空間，而狀態轉移函式取自在這個空間上的所有可能函式。拓撲自動機經常叫做M-自動機，簡單是半自動機加上接受狀態集合的補充，這裡的集合交集確定初始狀態是被接受還是被拒絕。

一般的說，自動機不需要嚴格的接受或拒絕一個輸入；它可以按某個在零和一之間的機率接受它。還是用量子有限自動機作為展示例子，它只按某個機率接受輸入。這個想法也是更一般情況幾何自動機或度量自動機的特殊情況，它的狀態的集合是度量空間，一個語言被這個自動機接受如果在初始點和接受狀態的集合之間的距離關於這個度量是足夠的小。

形式文法

在計算機科學中，形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。

形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設字母表只包含'a'和'b'兩個字元，初始符號是'S'，我們套用下述規則：

• 1. S -> aSb
  
• 2. S -> ba
  

於是我們可以通過把"S"重寫為"aSb"（規則1），我們還可以繼續套用這條規則把"aSb"重寫為"aaSbb"。這個重寫的過程不斷重複，直到結果中只包含字母表中的字母為止。在例子中，我們可以得到S -> aSb -> aaSbb -> aababb這樣的結果。由文法刻畫的語言，包含了所有可以這樣產生的字串，比如ba, abab, aababb, aaababbb等等。

喬姆斯基譜系

喬姆斯基體系是計算機科學中刻畫形式文法表達能力的一個分類譜系，是由諾姆·喬姆斯基於1956年提出的。它包括四個層次：

• 0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
  
• 1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裡的A是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
  
• 2-型文法（上下文無關文法）生成上下文無關語言。這種文法的產生式規則取如A-> γ 一樣的形式。這裡的A是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程式設計語言的語法提供了理論基礎。
  
• 3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個終結符號後隨一個非終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程式設計語言中的詞法結構。
  

正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這裡的包含都是集合的真包含關係，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。

下表總結了上述四種類型的文法的主要特點：

文法	語言	自動機	產生式規則
0-型	遞歸可枚舉語言	圖靈機	α -> β（無限制）
1-型	上下文相關語言	線性有界非確定圖靈機	αAβ -> αγβ
2-型	上下文無關語言	非確定下推自動機	A-> γ
3-型	正規語言	有限狀態自動機	A->aB; A->a