已知文法G:S→A0|81,A→S111,B→S010,其中S是开始符号。从S出发可以推导出(21)。

admin2021-01-13  12

问题 已知文法G:S→A0|81,A→S111,B→S010,其中S是开始符号。从S出发可以推导出(21)。

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

答案C

解析 从开始符出发,能推导出两种串:一种以0结尾,一种以l结尾。以0结尾的前面必须是1,而这个1前面可能还有一个递归的S;以1结尾的前面必须是0,而这个0前面可能还有一个递归的S。由此可以知道,这是文法可以导出某些0和1的个数相同的串。之所以说是某些,而不是所有,是因为,该文法所导出的串中0附近必有1,1附近必有0,比如:01,0101,0110等等。但000111就不能导出。
转载请注明原文地址:https://kaotiyun.com/show/vkCZ777K
0

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