首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。
admin
2013-05-11
28
问题
根据乔姆斯基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)。如果在交换过程中出现拥塞,该信息被记录在信
~IPv6地址12AB:0000:0000:CD30:0000:0000:0000:0000/60可以表示成各种简写形式,下面的选项中,写法正确的是()。
在CPU执行一段程序的过程中,Cache的存取次数为4600次,由主存完成的存取次数为400次。若Cache的存取周期为5ns,主存的存取周期为25ns,则CPU的平均访问时间为(3)ns。
已知有5个子网通过互联网相连,最多需要(14)个协议转换程序。
根据CCITT载波标标准,E1载波的数据传输为(20)。
如果一个公司有2000台主机,则必须给它分配(1)个C类网络。为了使该公司网络在路由表中只占一行,指定给它的子网掩码应该是(2)。(2011年上半年试题)(1)
在Linux系统中,采用(1)命令查看进程输出的信息,得到下图所示的结果。系统启动时最先运行的进程是(2),下列关于进程xinetd的说法中正确的是(3)。(2009年下半年试题)(3)
内存采用段式存储管理有许多优点,但__________不是其优点。(2008年上半年试题)
IPv4地址是由网络号和主机号两部分组成的。以下选项中,(173)不能作为目标地址,(174)不能作为源地址,(175)只能用于本机测试,(176)只能用于内部网络。IM使用了更大的地址空间,每个地址占有128比特,为方便网络管理人员阅读和管理,采用(17
随机试题
下列有关基底细胞癌的说法正确的是
A.乌梅与阿司匹林B.乌贝散与头孢拉定C.石膏与四环素D.麻黄与呋喃唑酮E.大黄与利福平能减少药物排泄的中西药联用药组是()。
甲公司董事会作出一项决议,部分股东认为该决议违反公司章程,欲通过诉讼请求法院撤销董事会的决议。这些股东应当如何提起诉讼?(2006—卷三—43,单)
下列不需要按刚性角要求设计的基础形式是()。
银行代理信托往往采用()的模式进行。
协议并购、要约并购、二级市场并购是按照()划分企业并购。
MatchtheexamplesentenceswiththefunctionslistedA—F.Thereisoneextraoptionwhichyoudonotneedtouse.Examplesentenc
衡量一个劳教所工作水平的根本因素是()。
A、B是局域网上两个相距1km的站点,A采用同步传输方式以1Mb/s的速率向B发送长度为200000字节的文件。假定数据帧长为128比特,其中首部为48比特;应答帧为22比特,A在收到B的应答帧后发送下一帧。传送文件花费的时间为(15),有效的数据速
ArnoldParker43LeonardStreetAtlanta,GA02109Date:July20DearMr.Parker,Iamwritingtowithdrawmymembershipfrom
最新回复
(
0
)