首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
admin
2019-06-12
40
问题
根据乔姆斯基于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://kaotiyun.com/show/1oCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
通常情况下,信息插座的安装位置距离地面的高度为(25)cm。
配置POP3服务器时,邮件服务器的属性对话框如下图所示,其中默认情况下“服务器端口”文本框应输入__________。(2010年上半年试题)
由DHCP服务器分配的默认网关地址是192.168.5.33/28,(53)是本地主机的有效地址。
以太网的最大帧长为1518字节,每个数据帧前面有8个字节的前导字段,帧间隔为9.6μs,对于10BASE-5网络来说,发送这样的帧需要多少时间?(64)
在快速以太网物理层标准中,使用两对五类无屏蔽双绞线的是__________。(2009年上半年试题)
下面4种编码方式中属于差分曼彻斯特编码的是(15)。
阅读以下说明和C++代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplor
识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述,完成图10-4中的(1)~(6)。请从表10-2中选择方法,完成图10-5中的(7)~(10)。
阅读下列Java程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】StringEditor类的功能是:已知一个字符串,返回将字符串中的非字母字符都删除后的字符串。public(1){publicstati
阅读下列说明和图,回答问题1到问题3。[说明]目前大多数操作系统都采用虚拟存储技术,这样可在较小的可用内存中执行较大的用户程序,可在内存中容纳更多程序并发执行。引入虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个
随机试题
腹股沟直疝和斜疝的共同点是
下列哪项不是甲状腺乳头状癌的常见特征?
女,29岁,近1个月来关节疼痛,局部灼热红肿,痛不可触,关节活动不利,伴发热恶风,口渴、烦闷、苔黄燥,脉滑数。中医的辨证分型是
流式细胞仪采集的荧光信号反映
输卵管绝育术并发症不包括
不属于湿法制粒的制备工艺是()。
根据表7中给出的备选场址初步调查情况,应选用哪个场址?请说明理由,并进一步指出拟选用场址的制约因素和解决措施。为进一步论证选址的合理性,还必须调查补充哪些基本情况?
客户交易终端信息不包括()。
设学生S、课程C、学生选课SC的关系模式分别为:S(Sno,Sname,Sage,Saddr)、C (Cno,Cname,Pcno)以及SC(Sno,Cno,Grade),与关系代数表达式πSno,Sname,Grade (σSnam=’数据库’,(S|×
ChristophePetytissittinginaPariscafe,listingtheadornmentsofhisprivateartcollection;severalVanGoghs,andacomp
最新回复
(
0
)