2. 计算机
  3. 文法G=(VT，VN，P,S)的类型由C中的(32)决定。若GO=({a，b}，{S，X，Y}，P,S)，P中的产生式及其序号如下： 1：S→XaaY 2：X→Dqb 3：Y→XbXla 则GO为(33)型文法，对应于(34)，由G

文法G=(VT，VN，P,S)的类型由C中的(32)决定。若GO=({a，b}，{S，X，Y}，P,S)，P中的产生式及其序号如下： 1：S→XaaY 2：X→Dqb 3：Y→XbXla 则GO为(33)型文法，对应于(34)，由G

admin2010-01-23  54
问题 文法G=(VT，VN，P,S)的类型由C中的(32)决定。若GO=({a，b}，{S，X，Y}，P,S)，P中的产生式及其序号如下：
   1：S→XaaY
   2：X→Dqb
   3：Y→XbXla
   则GO为(33)型文法，对应于(34)，由GO推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为(35)和(36)。
选项 A、13133
B、12312
C、12322
D、12333
答案C
解析 形式语言的文法是一个4元组C=(VT，VN，P，S)，其中VT是非空有限集，称为终端符集；VN也是非空有限集，称为变量集；P为产生式集；3为起始符，S∈VN。形式语言的文法按户的特性可分成正则文法、上下文无关文法、上下文有关文法和图灵文法4种类型，又分别称为3型、2型、1型和0型文法。所对应的可实现的自动机分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。本题中给出的文法、生产式左部均是单个变量，因此是上下文无关文法。由此文法导出句子aaaaa的产生式号的序列及推导过程如下：
   S→XaaY1→YYaaY2→aYaaY3→aaaaa 3
   句子baabbb的推导过程为：
   S→XaaY1→baaY2→baaXbx3→baabbx 2→baabbb2因而产生式序号的序列是12333和12322。
转载请注明原文地址:https://jikaoti.com/ti/3Qa7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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