首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
文法G=(VT,VN,P,S)的类型由G中的(21)决定。若GO=({a,b},{S,X, Y},P,S),P中的产生式及其序号如下: 1:S→XaaY 2:X→YY|b 3:Y→XbX|a 则GO为(22)型文法,对应于(23),
文法G=(VT,VN,P,S)的类型由G中的(21)决定。若GO=({a,b},{S,X, Y},P,S),P中的产生式及其序号如下: 1:S→XaaY 2:X→YY|b 3:Y→XbX|a 则GO为(22)型文法,对应于(23),
admin
2019-03-04
37
问题
文法G=(V
T
,V
N
,P,S)的类型由G中的(21)决定。若GO=({a,b},{S,X, Y},P,S),P中的产生式及其序号如下:
1:S→XaaY
2:X→YY|b
3:Y→XbX|a
则GO为(22)型文法,对应于(23),由GO推导出句子aaaa和baabbb时,所用产生式序号组成的序列分别为(24)和(25)。
选项
A、13133
B、12312
C、12322
D、12333
答案
C
解析
文法G是一个四元组
G={V
T
,V
N
,S,P}
其中V
T
是一个非空有限的符号集合,它的每个元素成为终结符号。V
N
也是一个非空有限的符号集合,它的每个元素称为非终结符号,并且有V
T
∩V
N
=Φ。S∈V
N
,称为文法G的开始符号。P是一个非空有限集合,它的元素称为产生式。所谓产生式,其形式为:α→β。α为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(V
T
∪V
N
)*,α≠ε,即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形如α→β,α→γ的产生式缩写为α→β|γ,以方便书写。
1956年,著名的语言学家Noam Chomsky根据对产生式所施加的限制的不同,把文法分成了四类,并定义了相应的四类形式语言。
0型文法
设G=(V
N
,V
T
,P,S),如果它的每个产生式α→β是这样一种结构:α∈(V
N
∪V
T
)*且至少含有一个非终结符,而β∈(V
N
∪V
T
)*,则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任何0型文法语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中限制最少的一个。
1型文法
1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上,每一个α→β都有|β|≥|α|。这里的|β|表示β的长度。
注意:虽然要求|β|≥|α|,但有一特例:α→ε地满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法。
2型文法
2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β有α是非终结符。如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而 Ab不是一个非终结符。
3型文法
3型文法也叫正则文法,它对应于有限状态自动机。它是在2型文法的基础上满足: A→α|αB(右线性)或A→α|Ba(左线性)。
如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导为:A->ab, A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB,则不符合3型文法的要求。具体说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合,如果后面的ab改成一个非终结符就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。
注意:上面例子中的大写字母表示非终结符,而小写字母表示终结符。
本题中给出的文法、产生式左部均是单个变量,因此是上下文无文法。由此文法推导出句子aaaaa的产生式的序列及推导过程如下:
S→XaaY(使用1式)
→YYaaY(使用2式)
→aYaaY(使用3式)
→aaaaY(使用3式)
→aaaaa(使用3式)
句子baabbb的推导过程为:
S→XaaY(使用1式)
→baaY(使用2式)
→baaXbX(使用3式)
→baabbX(使用2式)
→baabbb(使用2式)
因此产生式序号组成的序列分别是12333和12322。
转载请注明原文地址:https://kaotiyun.com/show/yDTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
WBS是一种以()为导向的分析方法,用于分析项目所涉及的工作。
某项目工期为一年,项目经理对负责项目工作分解结构编制的小张提出了如下要求或建议,其中()是不妥当的。
某公司在项目执行过程中,对项目需求进行收集分析,并形成正式的项目文档,并由客户签字确认,但在交货时发现,实际产品与客户的要求大相径庭,客户拒绝付款。经调查研究发现,需求来源和低层需求实现不完全匹配,这最可能是在()方面出了问题。
某企业需要采用甲、乙、丙三种原材料生产Ⅰ、Ⅱ两种产品。生产两种产品所需原材料数量、单位产品可获得利润以及企业现有原材料数如表18-2所示。则公司可以获得的最大利润是()万元。取得最大利润时,原材料()尚有剩余。
在企业业务流程管理和重组过程中,及时和有效的评估是企业重要的学习途径。良好评估的基础是必须建立有效、公开、公认和公平的评估标准、评估指标和评估方法。评估标准和指标来源于公司的业务目标和流程要求,评估的方法主要关注()。
下面对项目组合管理的描述中,()是错误的。
对于工作规模或产品界定不太明确的外包项目,一般应采用()的形式。
某家具厂有方木材90m3,木工板600m3,生产书桌和书柜所用材料数量及利润如下表:在生产计划最优化的情况下,最大利润为(68)元。
某工程的进度计划网络图如下,其中包含了①~⑩10个结点,结点之间的箭线表示作业及其进度方向,箭线旁标注了作业所需的时间(单位:周)。设起始结点①的时间为0,则结点⑤的最早时间和最迟时间分别为(68)周。
以下内容中,(46)是采购计划编制的工具与技术①专家判断②项目范围说明书③自制/外购分析④项目章程⑤合同类型
随机试题
直到临界反向击穿电压前,稳压二极管都具有很高的()。
A.K+B.Na+C.Cl-D.Ca2+E.Mg2+心肌收缩中起关键作用的离子是
心脏压塞是心包穿刺的主要指征。
低渗性缺水应给等渗性缺水应给
两地汤的药物组成除有地骨皮、生地以外,还有
患儿,女,10岁。主诉:下颌前牙松动时发现缺失,缺失牙间隙已明显缩小。拟采用哪种间隙保持器最为合适
治疗蛔虫引起蛔厥腹痛呕吐,肺虚久咳,宜首选()
为患者叩背的基本顺序是()。
生产经营单位建立、健全安全生产规章制度和操作规程的重要性体现在()。
我国教育史上第一次把美育列为教育的重要组成部分是在1958年。()
最新回复
(
0
)