编译原理(一道小证明题)

发布时间:2013-08-17 18:23:00作者:左潇龙阅读(799 )评论(5)

                    作者:zuoxiaolong8810(左潇龙),转载请注明出处,特别说明:本博文来自博主原博客,为保证新博客中博文的完整性,特复制到此留存,如需转载请注明新博客地址即可。

                    最近闲暇之余看看编译原理,娱乐一下,碰到一道小小证明题,于是心血来潮证明一下。

                    LZ也是数学专业毕业的,当初上大学时每天做的最多的就是多达N个黑板的证明题,可惜啊,时光是残酷的,现在已不复往日了。

                    不过看到证明题,尤其是简单的证明题,LZ积蓄了多年的数学细胞又被激发起来了,这就是青春啊,神马《致青春》的都弱爆了,总拿爱情说事,其实大学里还是有很多值得回忆的事的,比如证明题,LZ说这话会不会勾起了很多人的痛苦回忆。

                    不过小证怡情,大证伤身,太长的证明题我们就不鸟咯(其实是LZ证明不出来,囧)。

                    

                    编译原理-->题目原型:

                    1,证明:用下面文法生成的所有二进制串的值都能被3整除(提示:对语法分析树的节点使用数学归纳法)。

                                      num -> 11 | 1001 | num 0 | num num

                    2,上面文法是否能生成所有能被3整除的二进制串?

                    

                    1、分析:该文法的终止符集为{11,1001,0},非终止符集为{num},起始符号为num,规则集{num->11,num->1001,num->num 0,num->num num},由以上文法得到的二进制串,转换成抽象语法树之后,其叶子节点一定是11或者1001,而如果向树的根节点按照规则生成二进制串,则产生的方式有以下两种。

                           1)num 0

                           2)num num。

                          因而,我们只需要证明num 0 和num num的组合可以被3整除即可。

                          因为假设前者可以被证明,则语法树的任何一个节点都可以被3整除,并且在此基础上,所有组合方式都可以被3整除,故可得到此文法所得到的所有二进制串都可以被3整除。 

                          有了以上分析,那么证明过程非常简单。

                           证明:step 1:11和1001都可以被3整除(不解释)。

                                      step 2:若组合形式为num 0 ,因为 num 0 = 2 * num,故在step 1的前提下,num 0 的组合可以被3整除。

                                      step 3:若组合形式为num num,设num num为num1 num2 ,且num2为n位二进制串,则num num = num1 num2 = (2的n次方) * num1 + num2 ,故在step 1的前提下,num num的组合可以被3整除。

                                      step 4:综合step 1 、step 2 、step 3,由上述文法生成的所有二进制串都可以被3整除。

                      2、答案:非也,最显然的,0就无法由文法导出,另外非显然的,比如21=10101,也无法由文法导出,再比如给21乘个2,即42 = 101010,也无法导出,and so on。

                      

                      欧了,怡完情上床睡觉,各位晚安。                                  

                                                 

                                                                      


    版权声明:本文版权归作者(左潇龙)所有,欢迎转载。但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    1
    精彩
    0
    感动
    0
    搞笑
    0
    开心
    0
    愤怒
    0
    无聊
    0
    灌水
    0
    惊讶
#1楼     时间:2013-08-21 17:34:00      来源:DM张朋飞
#2楼     时间:2013-08-24 16:45:00      来源:需要
囧,从“编译原理-->题目原型”后都看不懂了。
#3楼     时间:2013-08-24 21:20:00      来源:王小帆
龙书上的题
#4楼     时间:2013-11-06 16:43:00      来源:不曾流泪的鱼
表示数学很渣的哭过...
#5楼     时间:2014-09-16 11:35:00      来源:催夜凉风
编译原理都忘光了。
发表评论

站内搜索

最新评论