乔姆斯基谱系

维基百科,自由的百科全书
跳转到: 导航, 搜索

乔姆斯基体系是刻画形式文法表达能力的一个分类谱系,是由诺姆·乔姆斯基1956年提出的。它包括四个层次:

  • 0-型文法(无限制文法或短语结构文法)包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串,这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别,后者是前者的一个真子集,是能够被一个总停机的图灵机判定的语言。
  • 1-型文法(上下文相关文法)生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号,而 α, β 和 γ 是包含非终结符号与终结符号的字串;α, β 可以是空串,但 γ 必须不能是空串;这种文法也可以包含规则 S->ε ,但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
  • 2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号,γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
  • 3-型文法(正规文法)生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号;如果所有产生式的右侧都不含初始符号 S ,规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受,也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。

正规语言类包含于上下文无关语言类,上下文无关语言类包含于上下文相关语言类,上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系,也就是说:存在递归可枚举语言不属于上下文相关语言类,存在上下文相关语言不属于上下文无关语言类,存在上下文无关语言不属于正规语言类。

下表总结了上述四种类型的文法的主要特点:

文法 语言 自动机 产生式规则
0-型 递归可枚举语言 图灵机 无限制
1-型 上下文相关语言 线性有界非确定图灵机 αAβ -> αγβ
2-型 上下文无关语言 非确定下推自动机 A -> γ
3-型 正规语言 有限状态自动机 A -> aB

A -> a

[编辑] 参考文献

  • Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
  • Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112
自动机理论: 形式语言和形式文法
乔姆斯基层级 文法 语言 极小自动机
类型 0 无限制 递归可枚举 图灵机
n/a (无公用名) 递归 判定器
类型 1 上下文有关 上下文有关 线性有界
n/a 附标 附标 嵌套堆栈
n/a 树-邻接 适度上下文有关 嵌入下推
类型 2 上下文无关 上下文无关 非确定下推
n/a 确定上下文无关 确定上下文无关 确定下推
类型 3 正则 正则 有限
每个语言或文法范畴都是其直接上面的范畴的真子集
::...
免责声明:
当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 人工从互联网中收集并分享;
内容版权归原作者所有;
本人对内容的有效性/合法性不承担任何强制性责任.
若有不妥, 欢迎评注提醒:

或是邮件反馈可也:
askdama[AT]googlegroups.com


点击注册~> 获得 100$ 体验券: DigitalOcean Referral Badge

订阅 substack 体验古早写作:


关注公众号, 持续获得相关各种嗯哼:
zoomquiet


自怼圈/年度番新

DU22.4
关于 ~ DebugUself with DAMA ;-)
粤ICP备18025058号-1
公安备案号: 44049002000656 ...::