2. 计算机
  3. 根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的

根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的

admin2019-06-12  41
问题 根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说，(3)最强，(4)最弱，由4类文法的定义可知(5)必是2型文法。
选项 A、0型文法
B、1型文法
C、2型文法
D、3型文法
答案D
解析 乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。0型文法也称短语文法，其能力相当于图灵(Turing)机，或者说任何0型语法都是递归可枚举的。1型文法也称上下文有关方法，其能力相当于线性有界自动机。2型文法也称上下文无关文法，其能力相当于非确定的下推自动机。3型文法也称为线性文法，由于这种文法等价于正规式，因此也称为正规文法。3型文法的能力相当于有穷自动机。自动机分为确定的自动机和非确定的自动机，一个非确定的自动机一定可以转化为一个与之等价的确定的自动机。0、1、2、3型文法是逐渐增加限制的，因此，0、1、2、3型文法描述语言的能力依次递减。也正因为此，每一种3型文法也一定是2、1、0型文法，每一种2型文法也一定是1、0型文法，每一种1型文法也一定是0型文法。
转载请注明原文地址:https://jikaoti.com/ti/qTG7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)