![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/langzh-mo-640px-Chomsky-hierarchy.svg.png&w=640&q=50)
杭士基譜系
維基百科,自由的 encyclopedia
杭士基體系是電腦科學中刻畫形式文法表達能力的一個分類譜系,是由語言學家諾姆·杭士基於1956年提出的。它包括四個層次:
- 0-型文法(無限制文法或短語結構文法)包括所有的文法。該類型的文法能夠產生所有可被圖靈機辨識的語言。可被圖靈機辨識的語言是指能夠使圖靈機停機的字串,這類語言又被稱為遞歸可列舉語言。注意遞歸可列舉語言與遞歸語言的區別,後者是前者的一個真子集,是能夠被一個總停機的圖靈機判定的語言。
- 1-型文法(上下文相關文法)生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裏的A 是非終結符號,而 α, β 和 γ 是包含非終結符號與終結符號的字串;α, β 可以是空字串,但 γ 必須不能是空字串;這種文法也可以包含規則 S->ε ,但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
- 2-型文法(上下文無關文法)生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這裏的A 是非終結符號,γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程式語言的語法提供了理論基礎。
- 3-型文法(正規文法)生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號,產生式的右側只能是空字串、一個終結符號或者一個終結符號後隨一個非終結符號;如果所有產生式的右側都不含初始符號 S ,規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受,也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程式語言中的詞法結構。
![]() | 此條目需要精通或熟悉相關主題的編者參與及協助編輯。 |
![]() | 此條目包含過多行話或專業術語,可能需要簡化或提出進一步解釋。 |
正規語言類包含於上下文無關語言類,上下文無關語言類包含於上下文相關語言類,上下文相關語言類包含於遞歸可列舉語言類。這裏的包含都是集合的真包含關係,也就是說:存在遞歸可列舉語言不屬於上下文相關語言類,存在上下文相關語言不屬於上下文無關語言類,存在上下文無關語言不屬於正規語言類。
![The Chomsky hierarchy](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/640px-Chomsky-hierarchy.svg.png)
下表總結了上述四種類型的文法的主要特點:
More information 文法, 語言 ...
文法 | 語言 | 自動機 | 產生式規則 |
---|---|---|---|
0-型 | 遞歸可列舉語言 | 圖靈機 | α -> β(無限制) |
1-型 | 上下文相關語言 | 線性有界非確定圖靈機 | αAβ -> αγβ |
2-型 | 上下文無關語言 | 非確定下推自動機 | A -> γ |
3-型 | 正規語言 | 有限狀態自動機 | A -> aB A -> a |
Close