首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
admin
2013-05-11
62
问题
根据乔姆斯基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
软件设计师上午基础知识考试
软考中级
相关试题推荐
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(22),校验和对(23)进行校验。信元交换采用(24)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(25)。如果在交换过程中出现拥塞,该信息被记录在信
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(22),校验和对(23)进行校验。信元交换采用(24)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(25)。如果在交换过程中出现拥塞,该信息被记录在信
PKI体制中,保证数字证书不被篡改的方法是(43)。
关于选用源路径选择桥的局域网,下列说法__________是正确的。
依据著作权法,计算机软件著作权保护的对象是指()。
10BASE—T以太网使用曼彻斯特编码,其编码效率为(1)%。在快速以太网中使用4B/SB编码,其编码效率为(2)%。(1)
OCSMA/CD协议可以利用多种监听算法来减小发送冲突的概率,下面关于各种监听算法的描述中,正确的是()。
确定网络的层次结构及各层采用的协议是网络设计中(59)阶段的主要任务。
设有三个指令系统相同的处理机X、Y和乙它们都有4KB的高速缓冲存储器和 32 MB的内存,但是其存取周期都不一样,如表2.11所示(TIC和TIM分别表示I处理机 Cahce存取周期和主存存取周期)。若某段程序所需指令或数据在Cache中取到的概率为P
Calculator is(66)for performing arithmetic operations, but that requires human intervention to alter its stored program, if any
随机试题
情景交融是意境创造的()
A.钙B.磷C.镁D.锌E.铁对神经、肌肉的兴奋性有镇静作用的是
审刑院
某工程的时标网络计划如图2一1所示。工程进展到第5个月底、第10个月底和第15个月底时,分别检查了工程进度,相应地绘制了三条实际进度前锋线,如图中的点划线所示。注:1.图中每根箭线上方数值为该项工作每月计划投资。2.图下方格内(1)栏
巴塞尔委员会建议计算风险价值时的持有期长度为()个营业日。
中国公民李某是境内甲非上市公司的个人股东兼董事,但未在甲公司任职。2015年相关业务如下:(1)1月李某从甲公司借款10万元,年末未归还也未用于甲公司生产经营活动;12月从甲公司分得股息5万元。(2)12月李某领取甲公司董事费收入12万元,从中
下列判断正确的有()。(1)“十一五”期间该地区每年“科研基建费”均多于“其他费用”(2)“十一五”期间该地区专业技术人员人均财政科技拨款逐年增加(3)“十一五”期间该地区财政科技拨款总和不到3500亿元
论述卢梭的儿童教育观。
下面程序段的执行结果是()。main(){inta[5][5],i,j;for(i=1;i<5;i++)for(j=1;j<5;j++)a[i][j]=(i<j)*(j/i);for(i=1;i<5;i
【B1】【B9】
最新回复
(
0
)