2. 计算机
  3. (2013年下半年上午试题21)已知文法G：S→A0｜B1，A→S1｜1，B→S0｜0，其中S是开始符号。从S出发可以推导出_______。

(2013年下半年上午试题21)已知文法G：S→A0｜B1，A→S1｜1，B→S0｜0，其中S是开始符号。从S出发可以推导出_______。

admin2021-01-13  62
问题 (2013年下半年上午试题21)已知文法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就不能导出。
转载请注明原文地址:https://kaotiyun.com/show/tXCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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