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

题库2022-08-02  25

问题 已知文法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

解析 对于文法可推导出的字符串分析,考试一般可对文法举例,然后总结规律。
以本题文法为例,可以产生的字符串包括:
(1)10
推导过程:S->A0;A->1。
(2)01
推导过程:S->B1;B->0。
(3)1010
推导过程:S->A0;A->S1:S->A0,A->1。
至此,可以了解到,选项A、B、D的描述都是不正确的。
转载请注明原文地址:https://tihaiku.com/congyezige/2410218.html

最新回复(0)