2. 从业资格
  3. 已知文法G:S->A0|B1,A->S1|1，B->S0|0，其中S是开始符号。

已知文法G:S->A0|B1,A->S1|1，B->S0|0，其中S是开始符号。

admin2022-08-02  15
问题 已知文法G:S->A0|B1,A->S1|1，B->S0|0，其中S是开始符号。从S出发可以推导出（ ）？A.所有由0构成的字符串B.所有由1构成的字符串C.某些0和1相等的字符串D.所有0和1个数不同的字符串
选项 A.所有由0构成的字符串
B.所有由1构成的字符串
C.某些0和1相等的字符串
D.所有0和1个数不同的字符串
答案 C
解析 用文法表示语言的语法规则时，推导是产生语言句子的基本方式。以题目中的文法为例，有如下推导：
1010：S=>A0=>S10=>A010=>1010 0110：S=>A0=>S10=>B110=>0110
然而0000，1111，1100，0011则推导不出来。因为由S先推出A0以后再去推导A则必然产生一个与0相邻（在0左边）的1，而由S先推导出B1，则下一步必然要推导出一个与1相邻（在1左边）的0.这保证了当1出现的时候，马上就会出现0，或者反之。并且0和1的距离很近。分析更多类似的例子发现，只有C选项最合适。
故正确答案为：C
转载请注明原文地址:https://tihaiku.com/congyezige/2415252.html
本试题收录于： 中级 软件评测师题库软件水平考试初中高级分类

中级 软件评测师

软件水平考试初中高级

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