最短路径算法与正则语言的空性判定
2015-07-18姜盼崔艳荣
姜盼 崔艳荣
摘要：正则语言的空性判定方法除了传统的标记法外，还有另一种方法，那就是利用最短路径算法。通过对路径的判断，来证明正则语言的空性是否可判定。如果为空，则路径无限长，不为空，则路径是有限长的。该算法比标记法少了标记这一过程，减少了系统的开销，提高了正则语言的判定效率。
关键词：最短路径算法 ；正则语言；可判定性
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2015）12-0079-02
确定型有穷自动机能够识别的语言称之为正则语言。正则语言可以用有穷自动机的形式进行描述。本文研究算法求解问题的能力，因为有一些问题算法上能够求解，而另一些则不能[1]。我们的目的是研究算法可解性的局限。正则语言的空性问题是否是可判定的，这需要我们去证明。
最短路径的问题源出于交通运输等问题，对于n个城镇之间的公路所组成的公路网，从甲地到乙地是否有公路，若有多条公路可以到达时，走哪条路最近？花费最省？这些问题是我们最为关注的。最短路径可以定义为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。解决最短路的问题有Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。本文结合最短路径Dijkstra算法问题的求解来证明正则语言的空性可判定性。
1 正则语言的空性判定方法 ——标记法
1.1 有穷自动机（DFA）和正则语言
定义1 有穷自动机是一个5元组（Q，Σ，Γ，δ，q0，F）[2]，其中：
Q：一个有穷集合，叫做状态集。
Σ：一个有穷集合，叫做字母表。
δ：Q Σ→Q是转移函数。
q0： 起始状态，q0∈Q。
F：接收状态集，F Q。
设M=（Q，Σ，Γ，δ，q0，F）是一台有穷自动机，ω=ω1ω2…ωn是字母表Σ上的一个字符串。如果存在*Q中的状态序列r0，r1，…，rn，满足下述条件：
1） r0= q0
2） δ（ri， ωi+1）=ri+1，i=0，1，…，n-1
3） rn∈F
则M接受ω。
条件（1）说机器从起始状态开始，条件（2）说机器按照转移函数从一个状态到一个状态，条件（3）说如果机器结束在接受状态，则接受它的输入。如果A=﹛ω|M接受ω﹜，则称M识别语言A。
定义2如果一个语言被一台有穷自动机识别，则称它是正则语言[2]。
由于当M1对ω计算时进入的状态序列为
q0，q1，q1，q0，q2，q0，q0，q0，q1，q0
它满足上述3个条件，根据计算形式定义， M1接受ω。M1的语言是
L（M1）=﹛ω|除
因为M1识别这个语言，所以它是正则语言。
1.2 图灵机（TM）的形式定义
定义3 一个图灵机是一个7元组（Q，Σ，Γ，δ，q0，qaccept，qreject），其中：Q，Σ，Γ都是有穷集合[3]，并且：
Q：状态集。
Σ：输入字母表，不包括特殊空白符号 凵。
Γ：带字母表，其中：凵∈Γ，Σ Γ。
δ：Q Γ→Q Γ ﹛L，R﹜是转移函数。
q0：起始状态，q0∈Q。
qaccept：接收状态，qaccept∈Q。
qreject：拒绝状态，qreject∈Q且qaccept qreject。
图灵机M=（Q，Σ，Γ，δ，q0，qaccept，qreject）的计算方式如下：开始时，M以最左边的n个带方格接受输入ω=ω1ω2…ωn∈Σ*，带的其余部分是空白（即填以空白符）。读写头从最左边的带方格开始运行。注意，Σ不含空白符，故出现在带上的第一个空白符表示输入的结束。M开始运行后，计算根据转移函数所描述的规则进行。如果M试图将读写头从带的左端移出，即使转移函数指示的是L，读写头也停在原地不动。计算一直持续到它进入接受或拒绝状态，此时停机。如果二者都不发生，则M永远运行下去。
1.3 标记法证明正则语言的空性
下面定理证明了EDFA是可判定的，因而也就证明了问题“一个给定的有穷自动机的语言是否为空”是可判定的。
定理1 EDFA是一个可判定语言。
证明 DFA接受一个串当且仅当：从起始状态出发，沿着此DFA的箭头方向，能够到达一个接受状态。为检查这个条件，设计一个使用标记算法的TM M。
T=“对于输入，其中A是一个DFA：
1） 标记起始状态。
2） 重复下列步骤， 直到所有状态都被标记。
3） 对于一个状态，如果有一个到达它的转移是从某个已经标记过的状态出发的，则将其标记。
4） 如果没有接受状态被标记，则接受，否则拒绝。”
2 最短路径算法判定正则语言的空性
2.1 最短路径算法及其思想
Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点：以起始点为中心向外层层扩展，直到扩展到终点为止[4]。
主要思想[5]：设G=（V，E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，若源顶点为V0，则S={V0}），第二组为其余未确定最短路径的顶点集合（用U表示）。对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么可得从V0到Vj的最短距离为dist[j]=min{dist[j]，dist[i]+matriX[i][j]}。基于这个原理，则可分为如下步骤：
1） 从集合U中选择使dist[i]的值最小的顶点i，将i加入到S中；
2） 更新与i直接相邻顶点的dist值；
3） 直到S=V结束。
2.2 最短路径算法判定正则语言的空性
正则语言的空性判定除了标记法证明外，还可以用最短路径算法来证明，其过程如下：
1） 初始时，假设所有路径权值相同。S只包含起始状态q0，即S={ q0}，q0的距离为0。U包含除q0外的其他状态，即：U={其余状态}。
2） 从起始状态q0出发，沿着此DFA的箭头方向，在集合U中寻找其子节点qn，把qn加入S中（由于权值相同，子节点qn可能会有多个），则路径总数为每一个深度中子节点总数的乘积。
3） 将子节点qn作为父节点，寻找下一个深度中的子节点。
4） 重复步骤（2）（3），直到需找一条有限深度的路径。即正则语言若为空，则路径无限长，正则语言若不为空，则路径是有限长的。
3 结论
用最短路径算法来证明正则语言的空性是一个比较创新的方法，该算法在实现的基础上相比传统正则语言的判定方法——标记法有自己的优势。标记法比较麻烦的就是要考虑每一个状态，如果有一个到达它的转移是从某个已经标记过的状态出发的，则将其标记。而最短路径算法不用考虑，直接比较其深度即可。该算法提高了正则语言判定的效率，是一个比较理想的算法。
参考文献：
[1] Michael Sipser. Introduction to the Theory of Computation Second Edition[M]. China Machine Press， 2007.
[2] 王晓峰.有穷自动机状态极小化方法及正则语言判定优化[J].广西民族大学学报，2008，14（3）：81-84.
[3] 赵正平.图灵机及其构造研究[J].电脑知识与技术，2006：192-194.
[4] 陆锋.最短路径算法：分类体系与研究进展[J].测绘学报，2001，30（3）：269-275.
[5] 陈雨婕.用图示法解析最短路径算法[J].开发研究与设计技术，2007.
