喬姆斯基譜系檢視原始碼討論檢視歷史
| 喬姆斯基譜系 |
喬姆斯基體系是由諾·喬姆斯基於1956年提出的，是刻畫形式文法表達能力的一個分類譜系。
目錄
簡介
正規語言
主要特點
簡介
它包括四個層次：
0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裡的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
2-型文法生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這裡的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。
3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。
正規語言
正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這裡的包含都是集合的真包含關係，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。
主要特點
下表總結了上述四種類型的文法的主要特點：
文法 語言 自動機 產生式規則
0-型 遞歸可枚舉語言 圖靈機 無限制
1-型 上下文相關語言 線性有界非確定圖靈機 αAβ -> αγβ
2-型 上下文無關語言 非確定下推自動機 A -> γ
3-型 正規語言 有限狀態自動機 A -> aB
A -> a[1]
下表總結了上述四種類型的文法的主要特點：
文法 語言 自動機 產生式規則 0-型 遞歸可枚舉語言 圖靈機 無限制 1-型 上下文相關語言 線性有界非確定圖靈機 αAβ,->,αγβ 2-型 上下文無關語言 非確定下推自動機 A,->,γ 3-型 正規語言 有限狀態自動機 A,->,aB,A,->,a