可判定性

判定性问题

  考虑一下的三种问题

  1. 如何确定两个正则表达式定义了相同的语言
  2. 如何确定两个DFA识别的语言是否相同
  3. 如何确定一个DFA识别的语言包含有限还是无限多个单词?

我们称一个问题是有效可解(Effectively solvable)的,如果存在一个算法可以在有限多的步骤内给出问题的答案,该算法的运行必须是可预测的,也就是说对于任意输入都可以预测该算法的执行过程和步骤,比如排序就是有效可解的问题,因为存在至少一种算法在有限步内给出答案,当然也存在诸如“猴子排序”这种例外,类似猴子排序这种靠不停的猜来解决问题的算法无法的有限步内给出答案,因此不会被视作有效的解决方案。

定义
关于一个回答是“是”或“否”的问题的有效解决方案被叫做判定程序(Decision procedure),一个拥有判定程序的问题被称作是可判定的(Decidable)

如何判定两个正则表达式是否定义了相同的语言

定理1
M_n是具有n个状态的DFA,如果M_n至少接受一个字符串,则它至少接受一个字符串s,使得|s|\leqslant n
证明
最短路径显然不能包含回路,则起始状态和停机状态之间最多可能经历每个状态恰好一次,也就是经历n条边,此时接受的字符串长度恰好是n,其余情况下的长度都要小于n。同时这个定理展示了一个DFA种最短的单词至多有n-1个字母,因为从起始状态到停机状态,不经过任何回路的话要经过n-1个状态和n-1条边,也就是n-1个字母,如果起始状态同时也是停机状态,那么接受的最短字符串就是\varLambda,它的长度是0
Q.E.D.

  解决这个问题需要从另一个角度入手,有Kleene定理知道了每个正则表达式都有对应的DFA,对于正则语言L_1L_2,可以定义一个接受语言L_3=(L_1\cap\overline{L_2})+(\overline{L_1}\cap L_2)的DFA(由于L_1L_2都是正则的,因此L_3也一定是正则的,而且在第九章中已经给出了构造正则语言的交集和补集的算法),识别L_3的DFA将会识别在L_1但不在L_2中,或者在L_2但是不在L_1中的单词,如果L_1=L_2,那么L_3将不包含任何单词,对应的DFA也将不识别任何字符串(包括\varLambda)。构造完该DFA后,我们可以用来三种方法判断该DFA是否接受至少一个字符串

  1. 首先,每个合法的正则表达式至少接受一个字符串,算法非常简单,首先去掉正则表达式的\scriptsize *号,然后对于每一个+,去掉右边的部分以及+本身,接着再去掉括号和\boldsymbol{\Lambda}(定义\varLambda的正则表达式),就可以得到一个该正则表达式定义的语言中的一个单词,比如对于(a+b)(ab^\ast+ba^\ast)(b+\boldsymbol{\Lambda}),就可以得到aabb,而aabb就是被该正则表达式定义的语言中的一个单词。接下来考虑,在Kleene定理的证明过程中给出了如何将DFA转换为正则表达式的方法,在最后一步的时候,DFA将只剩下一个起始状态和一个停机状态,中间由若干标记了正则表达式的有向边相连,而每一条边上的正则表达式都代表了该DFA接受至少一个字符串,如果该DFA不接受任何字符串,则起始状态和停机状态之间不包含任何有向边,即,要么根本没有停机状态,要么停机状态从起始状态是不可达的,这种情况下就可以说L_1L_2相同,因为L_3对应的DFA不接受任何语言
  2. 每个DFA本身都是一个有向图,只需要判断在作为起始状态和某个停机状态的节点中,是否存在至少一条有向通路,即可判断该DFA是否接受至少一个字符串,类似算法有很多,比如广度优先搜索就是其中比较简单的一种
  3. 让所有长度小于N该DFA状态数的字符串在该DFA上运行一次,如果DFA不接受其中任何一个,则它不接受任何字符串(定理1)

顺带一提,问题1和2实际上是等价的,因为由Kleene定理可以知道正则表达式和DFA之间可以互相转换。因此以上三种办法都提供了判定性问题“如何确定两个正则表达式定义了相同的语言”和“如何确定两个DFA识别的语言是否相同”的判定程序,他们都可以在有限步骤内给出问题的答案,并且这些步骤在开始运行以前都是可预测,因此,可以给出如下定理

定理2
存在至少一个判定程序来判断

  1. 一个DFA是否接受至少一个字符串
  2. 两个DFA是否等价
  3. 两个正则表达式是否等价

有限性(Finiteness)

  考虑一个判定性问题,如何判断一个DFA定义的语言是否是有限的。有关这一点,可以先把对应的DFA转换成正则表达式,然后观察,凡是非空字符串的闭包都是无限的,因此如果该正则表达式中包含非空字符串的闭包,则该正则表达式定义的语言就是无限的,也就是说对应DFA定义的语言也是无限的。同时,也有另一种方法,基于DFA本身来判断语言的有限性

定理3
M_n是具有n个状态的有限自动机,则M_n识别无限语言,当且仅当它识别字符串w,使得n\leqslant |w|\lt 2n
证明

  1. 根据泵引理,w可以被划分为xyz,其中|xy|\leqslant n,因为wM_n接受,因此对于所有无限多个xy^kz,k\in\mathbb{N}^+,都会被M_n接受,因此M_n识别的语言是无限的
  2. 假设M_n接受无限语言L,则L中一定存在一个单词w使得|w|\gt n,使得它在M_n的路径中存在一个或多个回路,此时按照w的路径构造一个新的路径,只留下第一个回路的第一次循环,之后直接绕过其他的回路(也就是遇到进入回路的状态的时候接着往前走,不去进入回路中),其他部分不变,这样到达停机状态后,就构成了一个L中的单词w',考虑w'的长度,可能小于n,但是绝不可能大于2n,这是因为M_nn个状态,所以回路最多包含n个状态,也就是在回路上循环一次的字符串长度不大于2n-1(考虑一下回路包含n个状态时相当于从停机状态画一条边连接到起始状态,此时从起始状态出发,在回路上循环一次之后再停机经历的边数量是2n-1),此时
    1. 如果w'的长度大于等于n,那么此时的w'就符合定理的范围。
    2. 而如果w'的长度小于n,那么就在回路上多循环一次,因为回路的长度不大于n,而w'本身的长度又小于n,因此最终多循环一次之后的单词长度必定同样小于2n

1和2一起,完成了对该定理的证明
Q.E.D.

因此,判定DFA接受的是有限语言还是无限语言,只需要遍历所有长度在[n,2n)中的字符串,看是否存在一个被DFA接受即可,如果没有,则语言就是有限的,如果有,则语言就是无限的

定理4
存在至少一个判定程序来回答有关DFA识别的语言的有限性问题
证明
M_n是有n个状态的DFA,识别|\Sigma|=m的语言L,则总共有m^n+m^{n+1}+m^{n+2}+...+m^{2n-1}个单词的长度不小于n并且小于2n,遍历这些单词,判断其中是否有至少一个被M_n接受,如果是,则L是无限的,否则L是有限的

虽然一般来说转换成正则表达式来解决这个问题要更加迅速,但是上述的方法的确是另一种有效解,它可以保证在m^n+m^{n+1}+m^{n+2}+...+m^{2n-1}步内给出答案。


乱我心者,今日之日多烦忧