首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
admin
2013-05-11
72
问题
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说,(68)最强,(69)最弱,由四类文法的定义可知:(70)必是2型文法。
选项
A、0型文法
B、1型文法
C、2型文法
D、3型文法
答案
D
解析
乔姆斯基把文法分成四种类型,即:0型、1型、2型、3型。0型文法也称短语文法,0型文法的能力相当于图灵机(Turing)或者说任何0型语言都是递归可枚举的。1型文法也称上下文有关方法,其能力相当于线形界限自动机,对非终结符进行替换时不必考虑上下文,并且一般不允许替换成空串ε。2型文法也称上下文无关文法,其能力相当于非确定的下推自动机。3型文法也称右线性文法,由于这种文法等价于正规式,所以也称正规文法。3型文法的能力相当于有限自动机。从文法描述语言的能力来说,0型文法最强,3型文法最弱。
语言的文法可以表示成一个四元组(VT,VN,S,P)。由3型文法的定义:一个文法G式3型文法,如果G是二型文法,并且G的每个产生式A→αB或A→α,其中α∈V*T,A,B∈VN,可知3型文法必是2型文法。
转载请注明原文地址:https://kaotiyun.com/show/1IRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最适应的软件开发方法是(13)。
单个磁头在向盘片的磁性涂料层上写入数据时,是以______ 方式写入的。
RIP协议中可以使用多种方法防止路由循环,在以下选项中不属于这些方法的是______。
在DHCP服务器配置过程中,可以把使用DHCP协议获取IP地址的主机划分为不同的类别进行管理,下面划分类别规则合理的是(46)。
两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(1),使用会话密钥算法效率最高的是(2)。(2009年上半年试题)(1)
以太网中,当数据传输提高时,帧的发送时间要按比例缩短,这样有可能会影响冲突的检测。为了能有效地检测冲突,可以(1)或者(2)。快速以太网仍然遵循CSMA/CD,它采取(3)而将最大电缆长度减少到100m的方式,使以太网的数据传输速率提高到100Mb/s。
下图表示了某个数据的两种编码,这两种编码分别是(1),该数据是(2)。(2009年下半年试题)(2)
两个部件的可靠度R均为0.8,由这两个部件串联构成的系统的可靠度为(1);由这两个部件并联构成的系统的可靠度为(2)。(2)
网络管理基本模型是由网络管理者、网管代理、管理信息库等要素构成,下列选项属于网络管理者的操作是()。
设有三个指令系统相同的处理机X、Y和乙它们都有4KB的高速缓冲存储器和 32 MB的内存,但是其存取周期都不一样,如表2.11所示(TIC和TIM分别表示I处理机 Cahce存取周期和主存存取周期)。若某段程序所需指令或数据在Cache中取到的概率为P
随机试题
A、B两支球队举行篮球比赛,采取三场两胜制,假没不存在平局。A队在其主场获胜的概率为0.8,B队在其主场获胜的概率为0.7。已知第一场在A队的主场,第二场在B队的主场,第三场在A队的主场。则A队赢球的概率比B队赢球的概率大:
社会生产力发展水平是衡量社会进步的
患者51岁,宫颈刮片细胞学检查为巴氏Ⅲ级,阴道镜下多点活检为宫颈上皮重度非典型增生,最应采取何种治疗方法:
制定调剂室特殊药品管理制度的目的是切实落实特殊药品在调剂室的
铸造金属全冠颈部肩台的宽度通常为
为了解房价上涨情况,某课题组近日对北京、上海、广州和深圳的房价进行调查。这种调查属于()。[2014年初级真题]
下列投资工具中,适合用来筹备子女教育金的是()。
甲公司是增值税一般纳税人,2016年3月1日委托乙公司销售商品180件,商品已经发出,每件成本为70元。合同约定乙公司对外销售价格为每件120元,甲公司按不含增值税的销售价款的10%向乙公司支付手续费。3月20日乙公司对外实际销售100件。3月25日甲公司
韩信故乡淮安民间流传着一则故事——“韩信点兵”。秦朝末年,楚汉相争。有一次,韩信率1500名将士与楚军交战,战后检点人数,他命将士3人一排,结果多出2名;命将士5人一排,结果多出3名;命将士7人一排,结果又多出2名,用兵如神的韩信立刻知道尚有将士人数。已知
编写如下程序:PrivateSubForm_Click()DimiAsInteger,jAsIntegerDimnumAsIntegerDimarr(3,3)AsIntegernum=1
最新回复
(
0
)