已知文法G：S--AOIBI，A--S111，B—S0I0，其中S是開始符號。從S出發(fā)可以推導(dǎo)出（）。
A.所有由0構(gòu)成的字符串
B.所有由1構(gòu)成的字符串
C.某些0和1個數(shù)相等的字符串
D.所有0和1個數(shù)不同的字符串
正確答案：C
本題考查程序語言基礎(chǔ)知識。用文法表示語言的語法規(guī)則時，推導(dǎo)是產(chǎn)生語言句子的基本方式。以題目中的文法為例，推導(dǎo)出1010的過程為S=>AO=>S10=>A010=>101O，推導(dǎo)出0110的過程為S=>AO=>S10=>BIIO=>O11O，對于0000、1111、1100、0011等則推導(dǎo)不出。因為由S先推導(dǎo)出AO后，再去推導(dǎo)A則必然產(chǎn)生一個與0相鄰（在0的左邊）的1，而由S先推導(dǎo)出B1，則下一步必然要推導(dǎo)出一個與1相鄰（在1的左邊）的0。這保證了當(dāng)1出現(xiàn)時，馬上就會出現(xiàn)0，或者反之，且0和1的距離很近。分析更多的例子發(fā)現(xiàn)，僅有“某些0和1個數(shù)相等的字符串”是正確的。

點擊查看答案