《形式语言与自动机论文结构化程序设计思想在形式语言与自动机理论中的体现》由会员分享，可在线阅读，更多相关《形式语言与自动机论文结构化程序设计思想在形式语言与自动机理论中的体现（6页珍藏版）》请在金锄头文库上搜索。
1、关于结构化程序设计思想在形式语言与自动机理论中的体现一文中性质语言与自动机相关理论知识的分析与感悟戚洪源摘 要：本文为本科阶段学习形式语言与自动机课程过程中阅读专业文献后，对于该文献中所涉及的形式语言与自动机的专业知识进行解读和分析，以及一些个人在学习形式语言与自动机课程后的感悟。关键词：形式语言与自动机 结构化程序设计 计算机理论正 文：1、关于文献中形式语言与自动机相关知识的解读（1）文章第二部分涉及到的关于正则文法的相关知识文章的第二部分：构造文法时结构化思想的体现。在这一部分中，作者举了一个经典的正则文法的例子： MADMNPDBRS98.321098.0首先我们运用学过的知识将这个文
2、法转化为一个等价的正则文法：定义 2.5 若对于文法 G=(V,T,P,S),P 中每个产生式都有如下形式： VBATaBA,或则称 G 为正则文法。在这个文法中，除了第三行、第四行、第五行、第八行，每一个语句都满足正则文法语句的要求。而对于第五行，可以转化为： MN98.210第八行可以转化为： .31.DD第三行的转化为： BB.|98.3|21至于第四行，转化相对复杂一些，我用了如下的方法：引入新变量 EDP.0.,0,1,2,3.8,9为终结符有限集。到这一步为止，所有推出式都已经满足正则文法的要求，可见这个文法可以转化成等价的严格意义上的正则文法。我们可以看出，这个文法构造的语言其实
3、就是实数集，现证明了这个语言可以由一个等价的正则文法产生，因而可以判断，这是一个正则语言。定理 5.1 设 L 被某个正则文法 G 产生，则 L 可被某个有穷自动机接受。那么，我们来构造可以接受这个正则语言的有穷自动机：现将正则文法完整叙述出来：文法 G=（S,R,N,B,P,M,E,D，.,0,1,+,-，P,S）,其中 P为： 98.321.10|3|2.0DDBBMMNEPBRS现构造可以接受上述文法产生的正则语言的有穷自动机M。M=(S,R,N,B,P,M,E,D,f,.,0,1,+,-, ,S,f),其中：a)af( a|f|, TPBPCB， 对 一 切， 若满 足下面证明 M 可
4、以接受上述文法产生的正则语言：对于上述文法产生的语言，我们可以描述为，-,.1212 或为 cbacLmn那么可以由 M 经过如下推倒得到：1.L 为正数，且 L1， mnnn baDbaaBBRS . 2121*12121 22.L 为正数，且 L-1， mbbEPRS .0.021*1综上，L 均能被 M 接受，得证。上面，我们主要讲作者所举的这个“经典正则文法的例子”首先转化成了标准的、等价的正则文法，又写出了其对应的正则语言，并且构造了能够接受这个正则语言的 DFA。（2）文章第三部分涉及到的关于构造自动机的相关知识文献中对于识别语言 的自动机给出11,0|至 少 有 两 个且 xx了
5、两种答案。第一种答案构造的是一种 NFA，答案二是一种DFA，作者将这个问题转化到结构化程序设计过程，因而根据两种不同的思路，给出了两种答案。这里，我们运用形式语言与自动机的相关理论知识，将 NFA 转化为等价的 DFA:定理 3.1 设 L 是被一个非确定的有穷自动机接受的语言，则存在一个确定的有穷自动机也接受语言 L。已知接受该语言的 NFA M=(q1,q2,q3,s,0,1, ,s,q3),其中323121)1,(0,)(,),(qqS现在构造与其等价的 DFA , =( ),其中2M0 ,1,FqQ, 132123132 2323 SqSqSqSQ 0 , 132321321323
6、SqqF ,)1,(,)1,(,)1,(0 ,)0, ,)()()( ,), ,)1,1(1 ,)0,( ,0,() ,)0()1,(, ,0()(3123312312 3 131 1133 33 312212323122 33 223223122 12133 32 qqSqqqSS qSqqqqSSqqq 可见，按照课本定理构造的等价 DFA 比例二中的要复杂许多。但我们可将其进行化简。由于篇幅原因不再将其过程一一赘述。具体可按照课本 94 页“极小化算法”去解决，化简出来和第二种答案是一样的。(3)文章第三部分涉及到的关于正则语言运算的相关知识文章在这一部分运用了正则语言在并、乘积、闭包运
7、算下是封闭的，并且将每一种算法对应到结构化程序设计上去。具体对于定理的证明书上有原文，不再赘述。2、关于一些个人学习形式语言与自动机课程的体会和感悟不知不觉，形式语言与自动机这门课程也进入了尾声。作为计算机学科一门基础的理论学科，我必须承认，这门课程我没有学好、学透。从刚开课的时候，觉得这门课说的都是自己知道的一些简单知识，到后面突然之间不知所云冒出一大堆定义，再到后来的一堂课只讲一个定理的证明，直到现在，学完了这门课程，我才有了一点点概念：原来这就是形式语言与自动机。语言，由文法推出，四种文法，对应的四种语言，每一种语言又对应一种自动机可以接受。原来这门学科如此严谨，如此有规律。而我，一直没有领会到精髓，直到现在课程快结束。当初在国防科大学习数据结构也有这种感觉，第一次学不知道说的是啥，后来由于一些课程安排上的巧合，又再学习了一次。第二次学习，收货颇丰。所以，尽管这门课程结课了，但我一定会继续学习下去，我相信，一定可以从中收货许多珍贵的知识财富。
