形式语言与自动机论文

关于

《结构化程序设计思想在形式语言与自动机理论中的体现》 一文中性质语言与自动机相关理论知识的分析与感悟

————戚洪源

摘 要：本文为本科阶段学习形式语言与自动机课程过程中阅读专业文献后，对于该文献中所涉及的形式语言与自动机的专业知识进行解读和分析，以及一些个人在学习形式语言与自动机课程后的感悟。

关键词：形式语言与自动机 结构化程序设计 计算机理论 正 文：

一、关于文献中形式语言与自动机相关知识的解读 （一）文章第二部分涉及到的关于正则文法的相关知识

文章的第二部分：构造文法时结构化思想的体现。在这一部分中，作者举了一个经典的正则文法的例子：

S?R?R?R0R?NBPB?N.DP?0.DN?AMA?123...89M??0M1M2M3M...8M9MD?MA

首先我们运用学过的知识将这个文法转化为一个等价的正则文法：

定义2.5 若对于文法G=(V,T,P,S),P中每个产生式都有如下形式：

A?a或A?aB,a?T????,A,B?V

则称G为正则文法。

在这个文法中，除了第三行、第四行、第五行、第八行，每一个语句都满足正则文法语句的要求。而对于第五行，可以转化为：

N?0M1M2M...8M9M

第八行可以转化为：

D?0D1D2D...8D9D123...89

第三行的转化为：

B?1B|2B|3B...8B|9B|.D

至于第四行，转化相对复杂一些，我用了如下的方法： 引入新变量E

P?0E E?.D{.,0,1,2,3...8,9}为终结符有限集。到这一步为止，所有推出式都已经满足正则文法的要求，可见这个文法可以转化成等价的严格意义上的正则文法。

我们可以看出，这个文法构造的语言其实就是实数集，现证明了这个语言可以由一个等价的正则文法产生，因而可以判断，这是一个正则语言。

定理5.1 设L被某个正则文法G产生，则L可被某个有穷自动机接

受。

那么，我们来构造可以接受这个正则语言的有穷自动机： 现将正则文法完整叙述出来：

文法G=（{S,R,N,B,P,M,E,D}，{.,0,1,+,-}，P,S）,其中P为：

S?R?R?R0R?NBPP?0EE?.DN?0M1M2M...8M9MM??0M1M2M3M...8M9MB?1B|2B|3B...8B|9B|.DD?0D1D2D...8D9D123...89

现构造可以接受上述文法产生的正则语言的有穷自动机M。M=({S,R,N,B,P,M,E,D,f},{.,0,1,+,-},?,S,{f}),其中：

?(B,a)?{C|满足B?aC?P}?{f|若B?a?P}?(f，a)??，对一切a?T?{?}

下面证明M可以接受上述文法产生的正则语言： 对于上述文法产生的语言，我们可以描述为

L?ca1a2...an?1an.b1b2...bm?1bm,c为?或-，

那么可以由M经过如下推倒得到： 1.L为正数，且L>1，

S??R??B??a1B??a1a2B??a1a2...anB??a1a2...an.D??a1a2...an.b1D??a1a2...an.b1b2...bm**

2.L为正数，且L<1，

S??R??P??0E??0.D??0.b1D??0.b1b2...bm

*3.L为0,

S?0

4.L为负数，且L<-1，

S??R??B??a1B??a1a2B??a1a2...anB??a1a2...an.D??a1a2...an.b1D??a1a2...an.b1b2...bm**

5.L为负数，且L>-1，

S??R??P??0E??0.D??0.b1D??0.b1b2...bm

*综上，L均能被M接受，得证。

上面，我们主要讲作者所举的这个“经典正则文法的例子”首先转化成了标准的、等价的正则文法，又写出了其对应的正则语言，并且构造了能够接受这个正则语言的DFA。 （二）文章第三部分涉及到的关于构造自动机的相关知识

文献中对于识别语言{x|x?{0,1}?且x至少有两个1}的自动机给出了两种答案。第一种答案构造的是一种NFA，答案二是一种DFA，作者将这个问题转化到结构化程序设计过程，因而根据两种不同的思路，给出了两种答案。这里，我们运用形式语言与自动机的相关理论知识，将NFA转化为等价的DFA:

定理3.1

设L是被一个非确定的有穷自动机接受的语言，则存在一个

确定的有穷自动机也接受语言L。

已知接受该语言的NFA M=({q1,q2,q3,s},{0,1},?,s,{q3}),其中

?(S,?)?q1?(S,?)?q1?(q1,1)?{q1,q2}?(q1,0)?q1

?(q2,1)?{q2,q3}?(q2,0)?q2?(q3,0)?q3?(q3,1)?q3'现在构造与其等价的DFA M2,M2=(Q',{0,1},?',q0,F'),其中

Q'?{[q2],[q3],[q1],[q3,q2],[q1,q2],[q3,q1],[q3,q1,q2],[q3,q1,q2,S],?,[S],[q2,S],[q3,S],[q1,S],[q3,q2,S],[q1,q2,S],[q3,q1,S]}'q0?[S]

F'?[q3],[q3,q2],[q3,q1],[q3,q1,q2],[q3,q1,q2,S],[q3,S],[q3,q2,S],[q3,q1,S]

?'([q2],0)?[q2],?'([q2,S],0)?[q2],?'([q2,q3],0)?[q2,q3],?'([q2,q3,S],0)?[q2,q3]?'([q2,q3],1)?[q2,q3],?'([q2,q3,S],1)?[q2,q3],?'([q2],1)?[q2,q3]?'([q2,q1],0)?[q2,q1],?'([q2,q1,q3],0)?[q2,q1,q3],?'([q2,S],1)?[q2,q3]?'([q2,q1,S],0)?[q2,q1],?'([q2,q1,S,q3],0)?[q2,q1,q3],?'([q2,q1,S],1)?[q2,q1,q3]?'([q2,q1],1)?[q2,q1,q3],?'([q2,q1,q3],1)?[q2,q1,q3],?'([q2,q1,S,q3],1)?[q2,q1,q3]?'(?,0)?[?],?'([S],0)?[?],?'([q3],0)?[q3],?'([q3,S],0)?[q3]?'([q3],1)?[q3],?'([q3,S],1)?[q3],?'([?],1)?[?]?'([q1],0)?[q1],?'([q1,q3],0)?[q1,q3],?'([S],1)?[?]?'([q1,S],0)?[q1],?'([q1,S,q3],0)?[q1,q3],?'([q1,S],1)?[q2,q1]?'([q1],1)?[q2,q1],?'([q1,q3],1)?[q2,q1,q3],?'([q1,S,q3],1)?[q2,q1,q3] 可见，按照课本定理构造的等价DFA比例二中的要复杂许多。

但我们可将其进行化简。由于篇幅原因不再将其过程一一赘述。具体可按照课本94页“极小化算法”去解决，化简出来和第二种答案是一样的。

(三)文章第三部分涉及到的关于正则语言运算的相关知识 文章在这一部分运用了正则语言在并、乘积、闭包运算下是封闭的，并且将每一种算法对应到结构化程序设计上去。具体对于定理的证明书上有原文，不再赘述。

二、关于一些个人学习形式语言与自动机课程的体会和感悟 不知不觉，形式语言与自动机这门课程也进入了尾声。作为计算机学科一门基础的理论学科，我必须承认，这门课程我没有学好、学透。从刚开课的时候，觉得这门课说的都是自己知道的一些简单知识，到后面突然之间不知所云冒出一大堆定义，再到后来的一堂课只讲一个定理的证明，直到现在，学完了这门课程，我才有了一点点概念：原来这就是形式语言与自动机。语言，由文法推出，四种文法，对应的四种语言，每一种语言又对应一种自动机可以接受。原来这门学科如此严谨，如此有规律。而我，一直没有领会到精髓，直到现在课程快结束。当初在国防科大学习数据结构也有这种感觉，第一次学不知道说的是啥，后来由于一些课程安排上的巧合，又再学习了一次。第二次学习，收货颇丰。所以，尽管这门课程结课了，但我一定会继续学习下去，我相信，一定可以从中收货许多珍贵的知识财富。

本文来源：https://www.bwwdw.com/article/bwhf.html