已知文法G:S→A0|B1,A→S1|1,B→S0|0,其中S是开始符号。从S出发可以推导出( )。

admin2015-05-21  38

问题 已知文法G:S→A0|B1,A→S1|1,B→S0|0,其中S是开始符号。从S出发可以推导出(   )。

选项 A、所有由0构成的字符串
B、所有由1构成的字符串
C、某些0和1个数相等的字符串
D、所有0和1个数不同的字符串

答案C

解析 本题考查程序语言基础知识。用文法表示语言的语法规则时,推导是产生语言句子的基本方式。以题目中的文法为例,推导出1010的过程为S=>AO=>S10=>A010=>1010,推导出0110的过程为S:>AO=>S10=>B110=>0110,对于0000、1111、1100、0011等则推导不出。因为由S先推导出A0后,再去推导A则必然产生一个与O相邻(在O的左边)的1,而由S先推导出B1,则下一步必然要推导出一个与1相邻(在1的左边)的0。这保证了当1出现时,马上就会出现0,或者反之,且0和1的距离很近。分析更多的例子发现,仅有“某些0和1个数相等的字符串”是正确的。
转载请注明原文地址:https://kaotiyun.com/show/tIPZ777K
0

最新回复(0)