第27题: [单项选择]已知文法G:S→A0|B1,A→S1|1,B→S0|0,其中S是开始符号。从S出发可以推导出______。 A. 所有由0构成的字符串 B. 所有由1构成的字符串 C. 某些0和1个数相等的字符串 D. 所有0和1个数不同的字符串 参考答案:C 答案解析:[解析] 从开始符号出发,能推导出两种串:一种以0结尾,一种以1结尾。以0结尾的前面必须是1,而这个1前面可能还有一个递归的S;以1结尾的前面必须是0,而这个0前面可能还有一个递归的S。由此可以知道,这是文法可以导出某些0和1的个数相同的串。之所以说是某些,而不是所有,是因为,该文法所导出的串中0附近必有1,1附近必有0,比如:01,0101,0110等等,但000111就不能导出。