2. 计算机
  3. 已知文法G1=(VT={a,b,d}，VN={S，A，B}，S,P)，其中P为，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　S→dAB　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

已知文法G1=(VT={a,b,d}，VN={S，A，B}，S,P)，其中P为，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　S→dAB　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

admin2009-02-15  0
问题 已知文法G1=(VT={a,b,d}，VN={S，A，B}，S,P)，其中P为，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　S→dAB　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　A→aA|a　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　B→bB|ε　该文法生成的语言是(28)。
选项 A、{dambn|m≥0，n≥O}
B、{dambn|m≥1，n≥0}
C、{dambn|m≥0，n≥1}
D、{dambn|m≥1，n≥1}
答案B
解析 已知文法G=(VT，VN，S，P)，它所产生的语言定义如下：若有S(11)w，则称 w是文法G的一个句型。仅含终结符的句型是一个句子。语言L(G)是由文法G产生的所有句子组成的集合：
   L(G)={w|Sw且w∈VT*}
   推导的定义如下：
   设文法G=(VT，VN，S，P)，A→β∈P，γ，δ∈V*，则稀γAδ直接推导出γβδ，表示成
         
   这个定义告诉我们，若知道γAδ∈V*，根据A→β∈，可求出γβδ∈V*，方法是用A→β的右部β替换γAδ中的A得到γβδ；相反，若知道γβδ∈V*，根据A→β∈P，可求出γAδ∈V*，方法是用A→p的左部A替换γβδ中的β得到γAδ。
   若存在一个推导序列：，则称从a0经n步推导出an，表示成
     
   根据文法G1的第1条规则S→dAB知道，文法G1产生的句子的第1个字符是d，后跟着由A产生的终结字符串，再后边跟着由B产生的终结字符串。根据文法G1的第2条规则A→aA|a知道，由A产生的终结字符串是{am|m≥1}；根据B的规则B→bB|ε知道，由 B产生的终结字符串是{bn|≥0}。因此，L(G1)={dambn|m≥1，n≥0}。
转载请注明原文地址:https://kaotiyun.com/show/03xZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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