編譯原理-->題目原型：
?
1，證明：即時通訊 用下面文法生成的所有二進(jìn)制串的值都能被3整除（提示：對語法分析樹的節(jié)點(diǎn)使用數(shù)學(xué)歸納法）。
?
num -> 11 | 1001 | num 0 | num num
?
2，上面文法是否能生成所有能被3整除的二進(jìn)制串？

即時通訊：http://www.nanshan.biz/forum-38-1.html
?
?
1、分析：該文法的終止符集為{11,1001,0}，非終止符集為{num}，起始符號為num，規(guī)則集{num->11,num->1001,num->num 0,num->num num}，由以上文法得到的二進(jìn)制串，轉(zhuǎn)換成抽象語法樹之后，其葉子節(jié)點(diǎn)一定是11或者1001，而如果向樹的根節(jié)點(diǎn)按照規(guī)則生成二進(jìn)制串，則產(chǎn)生的方式有以下兩種。
?
?1）num 0
?
?2）num num。
?
因而，我們只需要證明num 0 和num num的組合可以被3整除即可。
?
因為假設(shè)前者可以被證明，則語法樹的任何一個節(jié)點(diǎn)都可以被3整除，并且在此基礎(chǔ)上，所有組合方式都可以被3整除，故可得到此文法所得到的所有二進(jìn)制串都可以被3整除。
?
有了以上分析，那么證明過程非常簡單。
?
?證明：step 1：11和1001都可以被3整除（不解釋）。
?
step 2：若組合形式為num 0 ，因為 num 0 = 2 * num，故在step 1的前提下，num 0 的組合可以被3整除。
?
step 3：若組合形式為num num，設(shè)num num為num1 num2 ，且num2為n位二進(jìn)制串，則num num = num1 num2 = (2的n次方) * num1 + num2 ，故在step 1的前提下，num num的組合可以被3整除。
?
step 4：綜合step 1 、step 2 、step 3，由上述文法生成的所有二進(jìn)制串都可以被3整除。
?
2、答案：非也，最顯然的，0就無法由文法導(dǎo)出，另外非顯然的，比如21=10101，也無法由文法導(dǎo)出，再比如給21乘個2，即42 = 101010，也無法導(dǎo)出，and so on。

總結(jié)

以上是生活随笔為你收集整理的小证明题 编译原理--题目原型：的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。