-
喬姆斯基文法
鎖定
- 中文名
- 喬姆斯基文法
- 外文名
- Chomsky hierarchy
- 別 名
- 喬姆斯基體系
喬姆斯基文法諾姆·喬姆斯基
艾弗拉姆·諾姆·喬姆斯基(英語:Avram Noam Chomsky,1928年12月7日-),或譯作“荷姆斯基”,美國哲學家、語言學家、認知學家、邏輯學家、政治評論家。喬姆斯基是麻省理工學院語言學的榮譽退休教授,他的生成語法被認為是20世紀理論語言學研究上的重要貢獻。他對伯爾赫斯·弗雷德裏克·斯金納所著《口語行為》的評論,也有助於發動心理學的認知革命,挑戰1950年代研究人類行為和語言方式中占主導地位的行為主義。他所採用以自然為本來研究語言的方法也大大地影響了語言和心智的哲學研究。他的另一大成就是建立了喬姆斯基層級:根據文法生成力不同而對形式語言做的分類。喬姆斯基還因他對政治的熱忱而著名,尤其是他對美國和其它國家政府的批評。從1960年評論越南戰爭以來,他的媒體和政治評論便越來越著名。一般認為他是活躍在美國政壇左派的主要知識分子。喬姆斯基把自己歸為自由意志社會主義者,並且是無政府工團主義的同情者。據藝術和人文引文索引説,在1980年到1992年,喬姆斯基是被文獻引用數最多的健在學者,並是有史以來被引用數第八多的學者。
[1]
喬姆斯基文法自動機理論
自動機是有限狀態機(FSM)的數學模型。FSM是給定符號輸入,依據(可表達為一個表格的)轉移函數“跳轉”過一系列狀態的一種機器。在常見的FSM的“米利型有限狀態機”(Mealy)變體中,這個轉移函數告訴自動機給定當前狀態和當前字符的時候下一個狀態是什麼。
逐個讀取輸入中的符號,直到被完全耗盡(把它當作有一個字寫在其上的磁帶,通過自動機的讀磁頭來讀取它;磁頭在磁帶上前行移動,一次讀一個符號)。一旦輸入被耗盡,自動機被稱為“停止”了。
依賴自動機停止時的狀態,稱呼這個自動機要麼是“接受”要麼“拒絕”這個輸入。如果停止於“接受狀態”,則自動機“接受”了這個字。在另一方面,如果它停止於“拒絕狀態”,則這個字被“拒絕”。自動機接受的所有字的集合被稱為“這個自動機接受的語言”。
但要注意,自動機一般不必須有有限數目甚至可數個狀態。比如,量子有限自動機有不可數無限個狀態,因為所有可能狀態的集合是在復投影空間中所有點的集合。所以,量子有限自動機和有限狀態機一樣,都是更一般想法拓撲自動機的特殊情況,它的狀態的集合是拓撲空間,而狀態轉移函數取自在這個空間上的所有可能函數。拓撲自動機經常叫做M-自動機,簡單是半自動機加上接受狀態集合的補充,這裏的集合交集確定初始狀態是被接受還是被拒絕。
一般的説,自動機不需要嚴格的接受或拒絕一個輸入;它可以按某個在零和一之間的概率接受它。還是用量子有限自動機作為展示例子,它只按某個概率接受輸入。這個想法也是更一般情況幾何自動機或度量自動機的特殊情況,它的狀態的集合是度量空間,一個語言被這個自動機接受如果在初始點和接受狀態的集合之間的距離關於這個度量是足夠的小。
[1]
喬姆斯基文法形式文法
形式文法描述形式語言的基本想法是,從一個特殊的初始符號出發,不斷的應用一些產生式規則,從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來説,假設字母表只包含'a'和'b'兩個字符,初始符號是'S',我們應用下述規則:
- 1. S -> aSb
- 2. S -> ba
於是我們可以通過把"S"重寫為"aSb"(規則1),我們還可以繼續應用這條規則把"aSb"重寫為"aaSbb"。這個重寫的過程不斷重複,直到結果中只包含字母表中的字母為止。在例子中,我們可以得到S -> aSb -> aaSbb -> aababb這樣的結果。由文法刻畫的語言,包含了所有可以這樣產生的字串,比如ba, abab, aababb, aaababbb等等。
[2]
喬姆斯基文法喬姆斯基譜系
- 1-型文法(上下文相關文法)生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裏的A是非終結符號,而 α, β 和 γ 是包含非終結符號與終結符號的字串;α, β 可以是空串,但 γ 必須不能是空串;這種文法也可以包含規則 S->ε ,但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
正規語言類包含於上下文無關語言類,上下文無關語言類包含於上下文相關語言類,上下文相關語言類包含於遞歸可枚舉語言類。這裏的包含都是集合的真包含關係,也就是説:存在遞歸可枚舉語言不屬於上下文相關語言類,存在上下文相關語言不屬於上下文無關語言類,存在上下文無關語言不屬於正規語言類。
[3]
下表總結了上述四種類型的文法的主要特點:
文法 | 語言 | 自動機 | 產生式規則 |
---|---|---|---|
0-型 | 遞歸可枚舉語言 | 圖靈機 | α -> β(無限制) |
1-型 | 上下文相關語言 | 線性有界非確定圖靈機 | αAβ -> αγβ |
2-型 | 上下文無關語言 | 非確定下推自動機 | A-> γ |
3-型 | 正規語言 | 有限狀態自動機 | A->aB A->a |
- 參考資料
-
- 1. Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)
- 2. Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112
- 3. Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:4次歷史版本
- 最近更新: DHY0620