2. 计算机
  3. 文法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)，

admin2019-03-04  41
问题 文法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)，由GO推导出句子aaaa和baabbb时，所用产生式序号组成的序列分别为(24)和(25)。
选项 A、13133
B、12312
C、12322
D、12333
答案C
解析 文法G是一个四元组
   G＝{VT,VN，S，P}
   其中VT是一个非空有限的符号集合，它的每个元素成为终结符号。VN也是一个非空有限的符号集合，它的每个元素称为非终结符号，并且有VT∩VN＝Φ。S∈VN，称为文法G的开始符号。P是一个非空有限集合，它的元素称为产生式。所谓产生式，其形式为：α→β。α为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(VT∪VN)*，α≠ε，即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形如α→β，α→γ的产生式缩写为α→β|γ，以方便书写。
   1956年，著名的语言学家Noam Chomsky根据对产生式所施加的限制的不同，把文法分成了四类，并定义了相应的四类形式语言。
   0型文法
   设G=(VN，VT，P，S)，如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则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://www.kaotiyun.com/show/yDTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)