有限状态自动机

又双叒叕一种新的定义语言的方法

一个有趣的比喻

  想象一下几个人一起玩大富翁,首先其中有一个人掷出骰子,然后该玩家根据掷出的点数来移动自己的角色若干步,抛开其他多余的规则和影响因素不谈,游戏的每一步变化都取决于骰子的点数,而游戏的胜负在一定程度上最终取决于骰子所生成的数字序列。
  让我们来把游戏的局势叫做状态,则当前的状态都会随着这些不同的点数而改变,对于1-6每个不同的点数,对应的棋盘上只有一种可能的状态,当然,游戏也允许对于多次掷骰的改变保持一个状态(对于大富翁来说就是入狱的时候,必须掷多次骰子才可能出狱,而这两次掷骰之间局势不变)。而类似的步骤重复若干次以后,游戏将会进入终局,也即一个玩家获胜,其他所有玩家破产。我们把这种状态叫做终局状态(Final State),在计算理论中,它被称为停机状态(Halting State)终止状态(Terminal State),或接受状态(Accepting State),而游戏则从一个初始状态(Initial State)出发,经过骰子所决定的状态的若干次变化,最终达到终局状态,也即一个玩家的胜利。

另一个有趣的比喻

  假如一个人有一台简单的计算机(包括I/O设备,CPU以及随机存取器(RAM)),我们假设他想要计算3+4的值,于是他写了一段程序,这段程序由一连串的指令构成(请类比汇编),每次计算机读取一条指令,然后执行这条指令,接着读取第二条指令,执行第二条指令。如果一切正常,那么这台计算机将会结束程序执行并输出7。这段过程和上述的大富翁游戏颇为类似,在这里,计算机就是棋盘,而游戏的局势就是内存中不同的数据布局,如果两台这样的机器内存布局一模一样,则他们就处于相同的状态
  这样的计算机是确定性的(Deterministic),也即意味着对于一个特定的指令输入,计算机将其转换为一个特定的状态(或者保持相同的状态如果给出的操作符是nop),这蕴含着每一个状态仅由它之前的那个状态和给定的指令所决定,不需要做出一些选择,也不需要知道若干个指令之前机器处于什么状态。对于3+4而言,一些指令序列可能会给出正确答案7,另外一些则不会,成功与否完全取决于指令序列包含的内容,和之前的大富翁游戏一样,这样的机器也有一个初始状态,若干个停机状态,我们的目的是打印出7这个数字,这才是最重要的,内存里的数据布局究竟是什么样子,这不要紧,而这两个例子的一个细微差别在于游戏的每一个状态都是临时决定的,而计算机的所有状态都是由输入的指令序列提前决定的。
  我们可以把大富翁游戏中骰子的所有可能点数作为一个字母表,对应点数就是字母表中的字母,那么就可以进一步定义出一个语言,这个语言包含了所有能够在游戏中获胜的字母序列所组成的字符串,对于计算机的例子来说,这个语言就是所有能够打印7的程序。

有限状态自动机的定义

  在上面的两种例子中都可以抽象出一个显而易见的,由起始状态,中间状态和停机状态所构成的模型,这种模型被叫做有限自动机(Finite Automata),或者有限状态自动机(Finite State Automata)或有限状态机(Finite State Machine)(这几种不同的称呼将会被频繁的混用),所谓"有限",指的是所有可能的状态是有限的,而作为输入的字母表(大富翁中的骰子,计算机程序中的指令)也必须是有限的;"自动",是因为这个模型如何运作完全取决于它的输入,对于每一个状态而言,下一个状态应该选择什么都是客观"自动"的,就像钟表指针的转动一样;而不是由某些主观意志决定的,就像是人类的行为一样

DEFINITION:
一个有限自动机(Finite Automaton,注: automaton是automata的单数形态)1由一下三者构成:
1. 一个包含了所有可能状态的有限集,其中包含一个起始状态(Initial/Start State),同样包含一些(可能是0个)停机状态(Haling/Final/Terminal/Accepting State)
2. 一个有限集,叫做字母表(Alphabet),用\varSigma表示,代表所有可能的输入字符
3. 一个状态转移规则(Transitions)的有限集,状态转移规则决定了对于每个状态和字母表的每个字符,应当如何选择下一个状态

目前为止,上述的定义并不完善,它仅仅定义了有限自动机是什么,但并没有描述它是如何工作的,有限自动机的工作需要一个输入字符串,自动机会从输入字符串的头部,一般来说是左侧开始,一个接一个的读取字符。这个输入字符串将会决定一系列的状态

EXAMPLE:
定义有限自动机\mathcal{M},令字母表\varSigma=\lbrace a,b\rbrace,状态集合\mathcal{S}=\lbrace x,y,x\rbrace,初始状态s_0=x,停机状态集合\mathcal{Z}=\lbrace z\rbrace并定义如下状态转移规则:
1. 对于状态x与输入字符a,转移状态至y
2. 对于状态x与输入字符b,转移状态至z
3. 对于状态y与输入字符a,转移状态至x
4. 对于状态y与输入字符b,转移状态至z
5. 对于状态z与任意输入字符,保持状态z

这样我们就定义了一个有限自动机,它满足所有三点要求,对于输入字符串aaa,该有限自动机会进行如下转换:

  1. Initial State x
  2. Read a, go to state y (Rule 1.)
  3. Read a, go to state x (Rule 3.)
  4. Read a, go to state y (Rule 1.)

到此,输入字符串被读取完毕,自动机运行结束,很明显我们的停机状态并非是z,因此这次运行是不成功的。
我们把所有能够让有限自动机\mathcal{M}终止在停机状态的字符串所构成的集合叫做被有限自动机\mathcal{M}所定义的语言,在上述语言中,字符串aaa不被\mathcal{M}所接受(not accepted by \mathcal{M}),这种情况下我们通常说aaa被有限自动机\mathcal{M}所拒绝(rejected by \mathcal{M}),我们把所有被\mathcal{M}所接受的字符串所组成的集合叫做\mathcal{M}对应的语言,称作有限自动机\mathcal{M}接受语言\mathcal{L}(注:这不仅要求该语言中的所有单词都可以被\mathcal{M}接受,而且要求该语言的所有字符串都可以被\mathcal{M}所接受),通俗一下来说,可以说有限自动机\mathcal{M}的语言是\mathcal{L},如果语言\mathcal{L_1}\sube\mathcal{L_2},则能够接受\mathcal{L_2}的有限自动机同样能接受\mathcal{L_1},但是并不能说该有限自动机接受\mathcal{L_1},因为这意味着该有限自动机能接受的所有输入都在\mathcal{L_1}中,忽略了不属于\mathcal{L_1}但属于\mathcal{L_2},并同样能被该有限自动机接受的部分。

  上面例子中的有限自动机所接受的语言实际上可以被如下正则表达式定义:

(a+b)^\ast b(a+b)^\ast

也就是至少包含一个字符b的语言,原因是该自动机可以转移到z状态当且仅当输入字符串中有至少一个b,而一旦进入z状态,就再也不可能转移到任何其他状态。
  由于定义所有可能的状态转移规则可能是非常冗长且麻烦的,因此我们可以用状态转移表(Transitions Table)来定义有限自动机,表中的每一行都对应一个状态,而每一列对应一个输入字符,而表的内容则是对于该列所表示的字母和该行所表示的当前状态,自动机将会转移到什么状态,对于上文中的例子,状态转移表就是这样的:

\begin{array}{c:cc}
& a & b \\ \hline
Start\ x & y & z \\
y & x & z \\
Final\ z & z & z
\end{array}

这也是一种定义有限自动机的方法,你可以在表的条目中填上任意你想要的状态,用来定义一个类似的自动机。
  接下来,我们可以用一种更加形式化的定义来定义有限自动机,也即把所谓的"状态转换集合"定义为一个一个函数\delta:

DEFINITION:
一个有限自动机是一个五元组\mathcal{M}=(\varSigma,\mathcal{S},s_0,\delta,\mathcal{F}),其中

  • 所有可能输入的字符的字母表\varSigma
  • 所有可能状态的集合\mathcal{S}
  • 初始状态s_0\in\mathcal{S}
  • 状态转移函数\delta:\mathcal{S}\times\varSigma\to\mathcal{S},其第一个参数为当前状态,第二个参数为读入的字符,输出为下一个状态
  • 所有可能的停机状态集合\mathcal{F}\sube\mathcal{S},可能为空

  虽然状态转换表相比起冗长而又复杂的列出规则要简洁得多,但是它仍然有缺点,那就是不能直观的从中看出状态转移关系,为了解决这个问题,可以引入一种图片来表示一个FA1,用小圆圈来表示状态,用连接在状态之间的箭头来表示状态转移关系,而对于每个箭头,我们会用能触发对应转换的字母来标记。如果一个字母触发的转换是从该状态转移到该状态自身,那么这个箭头也将会从代表该状态的圆圈出发并指向这个圆圈本身,这被叫做一个循环(Loop)。FA的初始和停机状态将会被特别指出,可以使用一个减号(-)或者文字标记初始状态,用加号(+)或者文字标记停机状态,另外一些既非初始又非停机状态的则什么也不标,这种演示图被叫做状态转换图(Transition Diagram),上述例子中的FA就可以用如下转换图表示2

对于字符串aaaabbabbaabbbb,该FA的状态转移分别如下:

应当注意到,状态转换图本身是一张有向图(Directed Graph),这些状态所在的位置叫做顶点(Vertice),而那些标志了状态转移的箭头叫做(Edge)3,每个状态都有与字母表中的字母数量相同的输出边(也就是那些源自该状态的边),而也可能有状态根本没有传入边(也就是指向该状态的边)

  这时候就出现了一个问题,考虑以下FA(对于\varSigma=\lbrace a,b\rbrace上的语言):

如果按照状态转换图来看,这个答案是确定无疑的,但是考虑到一点,那就是我们忽略了\varLambda,这一点看上去很迷惑,因为自动机是通过一个一个读取字符来执行对应操作的,而\varLambda不包含任何字符,在这里我们定义对于所有有限自动机,\varLambda都会开始并立刻结束于起始状态,而因为不接受字符串\varLambda,因此这个FA所接受的语言可以被如下正则表达式定义:

(a+b)^+

有几种FA是不接受任何语言的,第一种是没有停机状态的FA:

第二种是状态转换图并非连通图(Connected Graph)4的:

第三种是中间状态由于某种原因和停机状态是不连通的:

状态转换图(Transition Graphs)

DEFINITION
当一个字符串在没有被完全读取完毕的时候进入到一个没有任何它可以进行转换的输出边的状态,就说输入(或机器)在该状态崩溃,机器的执行将会被立刻终止,输入字符串会被拒绝

比如假设一种机器如下,他可以一次读1或2个字符

对于这样一个机器,字符串baa该被如何读取?如果我们一次读进去一个,那么最终就会停留在状态1,字符串不被接受,而如果我们第一次读进两个,那么就进入了一个没有任何规则告诉机器该如何转换状态的状态,因为起始状态1中并没有任何输出边是被标记了ba的,此时该机器就会崩溃。

对于这样的机器来说,我们无法决定一次该读进去几个字符,对于一个输入字符串可能有多种不同的路径可以选择,并且可能导致三种不同的后果:

  1. 选择的路径正确的抵达了停机状态,字符串被接受
  2. 选择的路径抵达了某一个非停机状态,字符串被拒绝
  3. 机器崩溃

此时我们没有办法再去判断这个字符串是否属于该机器对应的语言,因为这种问题的答案必须是严格的“是”或者“否”,而很显然以上三种状态导致该机器无法给出一个明确的答案,在这种情况下,这种机器所对应的语言就并非是良定义

  注意,有限自动机对于任何输入字符串都永远不可能崩溃,因为有限自动机的每个状态都有相对于字母表中的所有字母的边,也就是对于\varSigma=\lbrace a,b\rbrace上的语言,其有限自动机的每个状态都有一个a输出边和一个b输出边,即便是无限循环的状态,也有指向其自身的输出边,只要字符串还没有读完,机器就能继续下去

  让我们再来演示另一种奇怪的机器,这种机器同样每次可以接受不止一个字符:

很显然,字符串baab可以被该自动机接受,但是存在两种不同的接受方式,第一种是每次读取两个字符,按照1\rightarrow 2\rightarrow 4的顺序被读取,另一种是第一次读取三个字符,第二次读取一个字符,按照1\rightarrow 3\rightarrow 4的顺序被读取

在如上的例子中,和有限自动机不同,我们定义了一种可以一次读入多个字符的机器,我们把这种机器定义为转换图(Transition Graph)5,这种机器是在1957年被John Myhill所发明的

DEFINITION
一个状态转换图,简称TG,是一个五元组

  1. 所有状态的有限集\mathcal{S}
  2. 起始状态\mathcal{Q}\sube\mathcal{S},该集合包含至少一个元素
  3. 停机状态集合\mathcal{F}\sube\mathcal{S},可能为空
  4. 输入字符串可能会包含的所有字符所构成的字母表\varSigma
  5. 一个状态转移规则的有限集,状态转移规则指明了机器如何根据当前状态和读入的字符串(可能是\varLambda)来决定转移到哪个状态

注意,其中的第5条说明了读取的字符串,也就是边上的字符串并非只包含一个字符,他可能是空字符串\varLambda,也可以只有一个字符,也可能有多个字符;另外,每个状态可能不派生出任何转移规则(边),也可能派生出任意多个转移规则。

DEFINITION
一个状态转换图的成功路径(Successful Path),指的是构成从起始状态(可能有多个)到某个停机状态的路径的所有边的集合,我们按照顺序把所有边对应的字符串拼接起来,就可以得到一个可以被该机器接受的单词

在一个转换图中,如果一条边对应的字符串是\varLambda,那么在状态转换进行到这条边的时候,可以认为机器不读入任何字符(因为\varLambda)是空串。这蕴含着这种机器可以包含多个不同的起始状态,他们之间只需要使用标记了空串的边相连即可,比如

实际上是等价的,他们虽然拥有者不同的状态,但是识别的语言是相同的。
同时应当注意到,所有的FA都是TG,但并非所有的TG都是FA
考虑一下的TG:

很明显这个TG只接受字符串aa,但是却有无限种划分的方法,也就是有无限种路径可以让aa被该TG接受,并且可以发现,任何TG去掉由空串\varLambda构成的循环后依旧是一个能接受同样字符串的TG,我们之所以不禁止这种循环,是因为并非仅仅它可以做到产生无限种的路径:

这种由两个空串的边所构成的环路依旧可以产生无限多的路径,虽然对于这个,我们很明显能看出怎么移除环路,但是对于下面这种情形:

就比较特殊了,如果简单的移除掉包含空串的边,那么得到的TG将会与原TG接受不同结果的语言。不过事实上,所有包含\varLambda的边的TG都可以转换成另一个不包含\varLambda的边的TG,这点将在以后说明。

广义状态转换图

  可以定义一种更加自由的转换图,要求它的状态转换并不仅仅限于某个字符串,而是某个特定语言中的任意单词:

这其中从初始状态1转换到2的方法,是从\mathcal{L_1}的单词表(可能是无限的)中读有限多个单词,其他状态的转换也类似,当前我们并不会真的允许任意语言被当做转换规则,参考目前的学习进度,会把可以作为类似转换规则的语言限制到正则语言。

DEFINITION
一个广义状态转换图(Generalized Transition Graph)是一个五元组:

  1. 所有状态的有限集\mathcal{S}
  2. 起始状态\mathcal{Q}\sube\mathcal{S},该集合包含至少一个元素
  3. 停机状态集合\mathcal{F}\sube\mathcal{S},可能为空
  4. 输入字符串可能会包含的所有字符所构成的字母表\varSigma
  5. 连接两两状态的边(Edge),每个边都被标记上了一个正则表达式6

注意到广义状态转换图的边的正则表达式中可以包含闭包记号\scriptstyle *,这实际上和FA以及TG中的循环在功能性上是一样的,比如

实际上是一样的

非确定性

  广义状态转换图强迫我们思考另一个问题:既然一条边并非只接受一个字符并可以接受\varLambda,那么就可能存在两条路径导向相同的结果,比如

即便我们可以禁止两个边拥有完全一样的字符串,也有其他的方式来做到这一点

3\rightarrow 53\rightarrow 4\rightarrow 6识别的字符串完全相同,即便我们把每条边所能对应的字符串限制到单个字符或者\varLambda,也会有如下的情况

等价于

在状态转换图中,同样的字符串可能有多种不同的被接受路径,机器无法自行选择最终决定哪条路径,因此我们说这种机器是非确定性的(Nondeterministic),选择路径的过程掺杂进了人类的主观意识,而不再是有机器完全自动决定的


  1. 有限自动机(Finite Automata),或者其单数形式Finite Automaton,可以缩写为FA或者FAs,后者是前者的复数形式,类似的缩写还会经常见到 ↩︎ ↩︎
  2. 由于markdown语法支持的原因,这里采用另一种方式表示,也即起始状态使用一个实心圆圈指向(也就是被这个圆圈指向的是起始状态),而停机状态派生一个外层是黑色的同心圆(也就是停机状态会指向一个同心圆),同时这些状态使用方框而非圆圈表示 ↩︎
  3. 这里直接沿用了图论中的名词 ↩︎
  4. 此处又是图论概念,如果一张图中的任意两个顶点之间都有路径相连,那么这张图是连通图,否则是不连通的,注意对于有向图来说要求两个方向都有路径 ↩︎
  5. 此处用到的是Graph而非Diagram,应当注意到他们之间的区别,不要弄混 ↩︎
  6. 这一条类比之前提到的状态转移规则 ↩︎

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