计算复杂性 自动机模型

本节主要是介绍计算理论上的一些基本概念, 和一个最简单的计算模型, 即自动机模型. 自动机模型能解决的问题相当有限, 但是是图灵机模型的基础并且它足够简单, 因此以它作为一个入门是一个相当好的选择. 如果有学习过<算法导论>中的字符串匹配部分, 那么对这个概念应该并不陌生.

自动机模型和图灵机模型之间, 是下推自动机模型, 其功能强于自动机, 但弱于图灵机, 主要是程序语言理论中研究的核心模型, 我们暂且不研究程序语言理论, 因此也不介绍下推自动机.

计算, 就是解决某个具体问题的 算法 , 得出相应的答案. 计算机就是能执行某个具体算法的机器. 即Computer就用来是Compute的机器. 此外, 讨论什么是机器, 对我们研究计算机科学毫无帮助, 你只需要知道, 计算机就是用来执行算法的机器. 我们要做的就是, 用最简单的理论模型, 最大程度的抽象化我们现有的计算机.

例如字母表 , 则我们可以定义一个 上的语言 , 则该语言为

即所有的 都出现在任何 之前的串. 其中, 表示空串, 即长度为 的串.

这里要注意的是

我们也可用更加形式化的描述来定义语言.

这里要注意的是 不是空集, 而是含有一个特殊的元素 .

语言这个词可以说是一个相当糟糕的术语, 我们在这里不对这个术语本身进行过多的讨论, 但我们举例说明语言有多强大. 我们举一个有意义的例子.

例如, 一个语言可以用来表示所有的有向无环图, 我们试图用字母表 上的语言来对图进行编码. 首先我们需要表示图 中的 , 我们约定 之前的部分表示图中每个点的名称的长度 , 而 之后依次的每个长度为 的连续子串表示图所有点的名称. 在所有的名称后, 我们用另一个 作为分割, 其后依次的每个长度为 子串表示一条有向边. 所有的有向边后以 结束.

例如图

可以被表示为

在上述编码中, 作如下替换

即为该有向图的在该语言中的编码. 所有的有向无环图构成的语言, 即所有的有向无环图按照上述编码构成的语言. 值得一提的是, 上述语言对有向图的编码并不是双射, 但是我们可以增适当的限制使得该语言对有向图的编码成为双射.

按照类似的方式, 我们可以用语言表示, 所有的合取范式\无环布尔电路\树等. 大多数情况下, 我们不讨论具体的编码方式, 而是直接讨论语言, 如"所有的合取范式构成的语言".

计算理论中最简单的问题, 就是判定问题, 即只能用 回答的问题. 这类问题非常普遍, 例如问某个有向图是不是有向无环图, 那么这个问题的算法, 实际上是建立了一个映射. 如果用 表示所有的有向图构成的语言, 并用 分别表示 , 那么这个问题实际上就是建立了一个映射 , 且 当且仅当 . 而解决这个问题算法就是能够计算函数 的算法.

不难得出, 每一个语言都对应一个判定问题, 因此我们不再区分语言和判定问题, 我们可以直接说判定问题 , 即判定一个有向图是否为有向无环图的问题. 此后的绝大多数情况, 我们关心的问题都是判定问题.

有的读者会问, 为什么我们要如此关注判定问题? 因为在未接触到这方面理论的人的直观思维中, 判定问题是一类非常弱的问题, 弱到连自然数的加法都无法计算. 确实如此, 但是判定问题和非判定问题之间存在天然的关系, 每一个非判定问题都可以转换为判定问题. 例如, 计算问题 可以转换为判定问题 , 其中 当且仅当 , 即判定 是否为 和 的和的问题. 而且两者的复杂度之间存在深刻的关系, 我们将在之后的章节中具体介绍.

有限状态机也被称为自动机(automaton)，自动机不是什么复杂的东西, 一个自动机可以用一张类似于这样的图表示:

其中:

当有限状态机处于某个状态的时候, 读取到相应的符号, 有限状态机会根据转移函数跳转到下一状态. 例如上图中, 当有限状态机处于 状态时, 如果读到的下一符号为 , 根据转移函数 , 则在读取该符号后, 有限状态集仍会处于 状态

注意:

现在我们要讨论一类相当简单的语言, 和由它们构成的复杂度类 REG .

从上面有关于自动机的描述, 我们可以看到, 当自动机 处于起始状态 时, 我们输入一个 上的串 , 会依次读取串 上的符号, 并根据状态机作相应的状态转换. 当整个串 读取完毕后, 可能处于某个接受状态 , 也可能处于某个非接受状态 . 如果一个串 使 按照上述运行方式运行后, 处于某个接受状态, 就记 并称 接受 串 , 否则记 并称 拒绝 串 .

这里要注意拒绝状态有两种情况. 一种是在输入结束后, 自动机确实处于某个非接受状态. 另一种是, 在输入的过程中, 某一部计算根据状态和输入符号, 转移函数中并没有一条映射指出这种情况下机器应该转移到哪个状态. 即, 计算提前结束了.

根据这一点, 我们可以发现, 自动机 根据上述运行的方式, 可以表示一个映射 满足 当且仅当 . 如果一个语言 和一个自动机 满足 当且仅当 我们就说 识别 (recognize) 或 判定 (decide). 为了统一我们有关判定的问题的叙述, 我们总是使用"判定".

注意: 自动机是按照输入和转移函数按部就班地执行, 输入串中每一个符号都会让自动机执行一步, 且只会执行一步, 因此自动机总是在输入结束的时候停机, 因此不会出现不停机的情况. 在这样的限制下识别和判定是等价的, 但是对于其他的计算模型来说, 这两个概念并不等价.

现在我们定义一类判定问题(不要忘了一个语言对应一个判定问题, 判定问题的集合就是语言的集合)

即 REG 表示那些能够被一台自动机识别的语言.

例:

我们可以构造一台识别它的自动机来说明这一点

自动机可以被视为一台计算机, 但是是一台功能相当弱的计算机. 抽象能力比较强的读者可以发现, 自动机没有任何类似于内存的结构, 所有需要存储中间值的才能完成的判定问题都不能被自动机完成. 我们称一个计算模型能够解决问题的能力称为 计算能力 , 如果考虑的是判定问题, 那么它表示的就该模型能够判定的语言的集合的一些特征(如和其他模型能够判定的语言的).

现在我们语言的三种运算方式, 它们的运算结果仍是一个语言. 设 与 均为语言, 定义它们之间的三种运算:

即 是所有 中的串与 中的串拼接构成的串的集合, 在不产生歧义的时候, 这个圈可以不写. 根据concatenation的翻译, 我们可以称该运算为"串联".

它所表示的意义和集合的并集一样.

而 表示的是由 中的任意串重复任意次(如果重复 次就得到 )所得到的所有的串构成的集合. 例如 , 那么 等都是 的元素. 如果读者更倾向于形式化的定义, 那么 可以定义为

这三种运算称为 正则运算 , 我们不过度纠结运算的优先级问题, 并总是在需要的时候用括号表示运算的顺序.

现在我们来定义正则语言(regular language), 它包括一类最基本的语言, 和这类最基本的语言按照上述三种方式做运算产生的语言.

要注意的是, 4.5.6.表示的运算中, 空集也可以参与, 并且有:

这两点实际上也可以通过这些运算的定义得出.

如果是初次接触正则语言可能会觉得有些奇怪, 但是我们在学习正则表达式并了解自动机与正则语言的关系后, 这个概念会变得更加清晰.

从正则语言的定义种可以得到, 一个仅包含有限个串的语言总是一个正则语言, 因为它可以写成它的所有单个串构成的语言的 . 而每个单个串构成的语言又可以看作是仅有一个长度为1的串构成的语言的并联.

注意! 我们这里介绍的并不是用于在Linux系统中查询的正则表达式, 尽管我们介绍的正则表达式和它的功能一致. 但我们也会对Linux系统中的正则表达式某些符号的具体意思做出解释.

正则表达式(regular expression)是用来描述一个正则语言的, 它由字母表种的符号, 运算符, 运算符, 运算符还有括号组成. 我们可以用这些符号连同括号的组合来表示一个正则语言, 同样的, 这里的 在不产生歧义的情况下也可以略去不写.

例如, 正则表达式 , 表示语言

即所有长度为偶数且 只出现在从左至右第偶数位的串. 它的原理很简单, 它由长度为2单元 重复任意次组成, 而在一以个单元种, 第一位必须是0, 第二位可以是1或0. 实际上这个语言确实是正则语言, 令 , 那么有

显然复合正则语言的定义.

我们现在来定义正则表达式, 并用一些例子在说明它是如何运作的.

同时这里也要注意和空集的运算, 与正则语言类似, 这里不再赘述.

可以看出, 正则语言和正则表达式非常相似. 注意有时候, 我们会简化正则表达式的写法, 让整个串充当一个字母的角色, 并且可以用或( )连接一些串, 同时出现可选串 . 例如

表示语言

它的原理也非常简单, 每个串都是一些仅有字母表中一个符号构成的语言的串联, 而或( )表示的就是 , 而 表示的是 . 用这种方式表达的正则表达式, 就是我们常用于查询的正则表达式.

而如果或( )连接的是一些长度为1的串, 我们也更习惯将它表示为这些串的符号的集合, 例如 可以表示为 , 如果这个集合就是字母表 , 我们还可以写作 . 同时, 如果我们希望重复一个串 大于等于 次也可以用 来表示, 即 .

例子 设

其中3.中表示的正则表达式有助于屏蔽d幕中那些过长的类 串, 例如 .

注意 : 我们始终没有证明正则语言和正则表达式的对等性, 即一个正则表达式表示一个正则语言, 一个正则语言总可以用一个正则表达式表示. 我们不打算证明这一点, 因为我们认为读者的直觉能够察觉这一点, 如果喜欢学习严格的证明, 还是请阅读教材或论文.

非确定性(nondeterminism)是不是非确定自动机独有的, 我们还会在其他的计算模型中遇到非确定性, 因此我们决定先介绍非确定性, 再介绍非确定自动机.

在自动机模型中, 一个自动机在接受相同的输入时, 总是执行相同的计算步骤, 并总是得到相同的结果, 这样的计算方式称为确定的(deterministic). 即, 计算步骤与时间无关(如果我们将从宇宙大爆炸到目前为止的时间视作一个隐藏的参数的话/如果读者知道实时系统的定义, 那么对这个描述应该不会感到突兀). 这可能有点决定论的味道, 但也是一种理解方式. 反之, 非确定性, 就是, 一次具体的计算过程, 与时间有关. 或者, 我们可以更加直观地说, 一台具有非确定性的计算机, 在接受相同输入时, 计算步骤和结果可能有所不同.

自动机具有确定性是因为自动机处在任意状态时, 对于某个具体的输入, 根据转移函数, 改机器仅能转移到至多一个状态, 即转移的结果是唯一的. 如果我们修改这一条定义, 将转移的方式改为不确定的, 那么我们就得到非确定自动机(nondeterministic automaton).

为了避免读者对于陌生数学符号的恐惧, 我们解释一下 超集 . 有限集的超集非常容易理解, 一个有限集 的超集, 是它的所有子集的集合, 记作 . 例如 , 那么它一共有8个子集

其超集就是以上8个集合组成的集族(一般我们称集合的集合为集族, 也可简称为族).

这里与自动机相比, 唯一不同的一点在于转移函数, 非确定自动机的转移函数的上域(codomain)(注意不是值域!)变为了状态集 的超集 . 除此之外, 非确定自动机的转移函数还能接受输入 , 即在不接受任何输入的时候也可能随机发生转移. 回想一下, 自动机在处于某个状态时, 接受某个符号会转移到一个唯一确定的状态, 而处于某个状态的非确定自动机, 接受某个符号的输入, 则会有一些状态构成的集合作为"候选"状态, 非确定自动机会随机地从这些状态中选择一个进行转移.

如果我们将非确定自动机的每一次转移视作它产生了几个并行的计算分支, 那么我们由如下图所示的描述

其中左图为自动机的计算步骤, 其每一步计算都是仅产生一个计算分支, 而整个计算过程由一个计算分支过程, 自动机是否决定某个串, 取决于这个唯一的计算分支是否在串的输入结束后处于接受状态. 类似的, 我们通过这一点将接受的概念推广到非确定自动机上.

非确定自动机每一步都会产生多个计算分支, 而整个计算过程的计算分支可能会非常复杂. 非确定自动机的整个计算过程可以用一个深度和输入长度加1相等的树来表示, 其每个节点都是一个非确定自动机的状态, 而路径则是合法的转移. 通过这种方式, 我们可以知道, 每一条根到叶子的路径都是一条计算分支. 先在我们定义: 如果非确定自动机 在输入 时 存在 一条计算分支在输入结束后处于接受状态, 我们就说非确定自动机 接受输入 , 记作 . 否则, 我们称非确定自动机 拒绝串 , 记作 .

例如下面的非确定自动机, 处在 状态时, 可能会随机转移到 状态. 而当它处于 状态并收到输入 时, 可能转移到 或 状态. 当模拟其计算过程时, 可以计算通过将每一步机器可能处于的状态视作一个集合(我们称为合法状态集), 并在收到某个输入符号时, 计算每个合法状态集中的状态对应该符号根据转移函数得到的状态集合的并集. 例如下图中的非确定自动机根据输入

因此该非确定自动机应该是拒绝串 .

如果熟悉并行计算, 那么非确定自动机的计算步骤可以理解为"并行的", 即每一条计算分支相当于被非确定自动机并行的执行了. 需要注意的是, 计算分支数很可能是无限多的, 这样的机器在现实世界中也太可能被制造出, 但可以通过算法模拟.

从自动机与非确定自动机的定义可以看出, 自动机是非确定自动机中很特殊的一类机器, 相当于是机器处于任意状态时, 收到任意输入符号, 仅能转移到至多一个状态的非确定自动机.

现在我们通过建立一台指定任意非确定自动机 计算能力相同的自动机 , 来说明, 自动机和非确定自动的计算能力是相同的. 即

回想一下我们"合法状态集", 非确定自动机 处在某一步计算时, 在接受另一个输入, 可以视作从一个合法状态集转移到了一个另一个合法状态集, 而一个输入是否被接受, 取决于非确定自动机在该输入下最后一步计算对应的合法状态集中是否有接受状态, 因此我们通过这一点, 将一台非确定自动机 , 变为一台自动机 .

通过这样的转换, 我们容易证明, 当且仅当 .

令人惊奇的是, 任何一个正则语言, 都能被一台非确定自动机判定, 而任何一台非确定自动机判定的语言都是正则语言. 我们不打算证明这一点(因为教材上的证明非常详细), 但是会介绍一下如何将一个正则语言转换为判定它的非确定自动机.

广义非确定自动机**. 广义非确定自动机是非确定自动机的推广版本, 它的定义和非确定自动机类似. 唯一不同的一点在于, 其转移函数 表示的映射是

1、bots 和 bot 不含机器人的意思。

bots 是一种发生在动物中蝇蛆病

bot 是肤蝇的幼虫，如果大写为 BOT 则是 Beginning of Tape（磁带起始）的缩写。

2、机器人有以下三种：

android 指用生物材料做成的类似人形的机器人

automaton 以机械性的方式作出行为或反应的机器人

robot 能够按照指令或事先编好的程序做各种复杂人类工作的机械装置

正则表达式概述

正则表达式在程序设计语言中存在着广泛的应用，特别是用来处理字符串。如匹配字符串、查找字符串、替换字符串等。可以说，正则表达式是一段文本或一个公式，它是用来描述用某种模式去匹配一类字符串的公式，并且该公式具有一定的模式。

本小节将介绍正则表达式的基本概念、第一个正则表达式，以及测试正则表达式的工具Code Architects Regex Tester。

什么是正则表达式

正则表达式（Regular

Expression）起源于人类神经系统的早期研究。神经生理学家Warren McCulloch和Walter

Pitts研究出一种使用数学方式描述神经网络的方法。1956年，数学家Stephen

Kleene发表了一篇标题为“神经网事件的表示法”的论文，并在该论文中引入了“正则表达式”这一个概念。该论文称正则表达式是：“正则集的代数”的表达式。因此，采用“正则表达式”这个术语。正则表达式的定义存在多种说法，具体如下：

正则表达式就是用某种模式去匹配一类字符串的公式，主要用来描述字符串匹配的工具。

正则表达式描述了一种字符串匹配的模式。它可以用来检查字符串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。

正则表达式是由普通字符（如字符a到z）以及特殊字符（称为元字符）组成的文字模式。正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。

正则表达式就是用于描述某些规则的工具。这些规则经常用于处理字符串中的查找或替换字符串。换句话说，正则表达式就是记录文本规则的代码。

正则表达式就是用一个“字符串”来描述一个特征，然后去验证另一个“字符串”是否符合这个特征。

学过《编译原理》的读者可能知道不确定有限自动机（Non-deterministic

finite automaton，简称NFA）和确定有限自动机（Deterministic finite

automaton，简称DFA）。其实，正则表达式是一个不确定有限自动机。NFA和DFA的最大区别在于它们的状态转换函数。NFA可以对同一个字符串产生多种理解方式，而DFA则只有唯一的一种理解方式。也正因为如此，NFA在匹配过程中可能会回溯，NFA的效率一般要低于DFA。因此，在书写正则表达式时尽量减少回溯来提高正则表达式的效率。

如果你使用过Windows或DOS下用于文件查找的通配符*和?，那么你不难理解正则表达式。如果你需要查找所有Word文档，那么可能使用表达式*.doc。其中，字符*是一个通配符，它可以代表任意字符串。正则表达式和通配符具有相似性，它也可以使用一些字符（如字符.）表示任意字符。然而，它比通配符更具有精确性。

在正则表达式中，匹配是最常用的一个词语，它描述了正则表达式动作结果。给定一段文本或字符串，使用正则表达式从文本或字符串中查找出符合正则表达式的字符串。有可能文本或字符存在不止一个部分满足给定的正则表达式，这时每一个这样的部分被称为一个匹配。其中，匹配存在下面3种类型：

形容词性的匹配，即一个字符串匹配一个正则表达式。

动词性的匹配，即在文本或字符串里匹配正则表达式。

名词性的匹配，即字符串中满足给定的正则表达式的一部分。

正则表达式的应用非常广泛，特别是在字符串处理方面。目前来说，正则表达式已经在很多软件中得到广泛了应用，如Linux、Unix、HP等 *** 作系统，C#、PHP、Java等程序开发环境，以及很多的应用软件中，都可以看到正则表达式的这样或那样的应用。正则表达式常见的应用如下：

验证字符串，即验证给定的字符串或子字符串是否符合指定特征，譬如验证是否是合法的邮件地址、验证是否为合法的HTTP地址等。

查找字符串，从给定的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。

替换字符串，即把给定的字符串中的符合指定特征的子字符串替换为其他字符串，比普通的替换更强大。

提取字符串，即从给定的字符串中提取符合指定特征的子字符串。

---