新起点
乔姆斯基谱系
2020-06-11 09:47:40

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

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

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

->

相关:

  • 形式语言
  • 网站公告: