[科普中国]-有限自动机

基本介绍

有限自动机(finite automata)或称为有穷状态的机器，它由一个有限的内部状态集和一组控制规则组成，这些规则是用来控制在当前状态下读入输入符号后应转向什么状态.有限状态系统最初的形式研究是在1943年南McCulloeh和Pitts提出来的，有限自动机是一种数学模型，它可以用来描述识别输入符号串的过程，在这个机器中，它的状态总是处于有限状态中的某一个状态，系统的当前状态概括了有关历史的信息，这些历史信息对于后来的输入所能确定的系统状态是不可少的。简单地说，也就是要根据当前系统的状态和下一个输人的符号才能确定下一个状态。例如电梯的控制机构是有限自动机的一个例子，顾客的服务要求(即所要到达的楼层)是该装置的输入信息，而电梯所处的层数及运动方向则表示该装置的状态，这个机构并不记住所有先前服务要求，而仅仅记住是在几楼，运动的方向(上或下)及尚未满足的服务要求，在计算机科学中，可以找到许多有限状态系统的例子，如计算机本身也可以是认为是一个有限状态系统，尽管其可能状态数目很大，但仍然是有限的，有限自动机理论是设计这些系统的有效工具，研究有限状态系统的重要原因是概念的自然性和应用的广泛性，例如，在编译器中，人们主要用自动机来识别程序设计语言中的单词，但是它不能用来描述表达式、语句等复杂的语法结构。

有限自动机与正规文法和正规式有着非常密切的关系，它们的描述能力是相同的，因此，有限自动机是用来识别正规式的一个非常有用的工具，使用有限自动机来构造词法分析程序这也是一种比较好的途径。1

分类确定的有限自动机DFA定义1 一个确定有限自动机(DFA)M是一个五元组2

其中，

∑是一个有穷字母表，它的每一个元素称为一个输入符号；

S是一个有限状态集，它的每一个元素称为一个状态；

是转换函数，定义了从 上的一个单值映射，即 ，指明当前的状态为p，当输入符号为a时，则转换到下一个状态q，q称为p的后继状态；

是一个唯一的初始状态；

是一个终止状态集。

在状态转移的每一步，根据有限自动机当前所处的状态和所面临的输入符号，便能唯一地确定有限自动机的下一个状态，即转换函数的值是唯一的，反映到状态转换图上，就是若 ，则任何结点的出边都有n条，且这些出边上的标记均不相同，这就是为什么我们把按上述方式定义的有限自动机称为确定的有限自动机的原因。

定义2 DFA M所接受的符号串的集合称为DFA M所接受的语言，记为L(M)，即

换句话说，对于 中的任何一个串虬w,若存在一条从某一表示初态的结点到某一表示终态结点的通路，且这条路上所有弧的标记符依次连接成的符号串等于w，则称w可为DFA M所识别(读出或接受)。2

不确定的有限自动机NFA若有限自动机根据当前所处的状态和所面临的输入符号，能够确定的后继状态不是唯一的，就称这样的有限自动机为不确定的有限自动机。如图1是NFA，在这个NFA中，状态0在输入符号a时有两个可能的转移状态0，1。

我们一定已经注意到前述的DFA只是NFA的一种特殊情况，对于给定的输入字符串w和状态 ，在DFA中，恰好存在始于 标记为w，的一条路径，而在NFA中，却可能存在始于 ，标记为w的若干条路径2。

下面给出不确定有限自动机的形式定义如下：

定义 一个不确定有限自动机(NFA) M是一个五元组

其中，

是一个有穷字母表，它的每一个元素称为一个输入符号；

S是一个有限状态集，它的每一个元素称为一个状态；

是转换函数，定义了从 上的映射( 表示S的幂集)，即 ，指明当前的状态为p，当输入符号为a时，则转换到的状态是一个状态集；

是的初始状态集；

是一个终止状态集。

从NFA的定义可以看到，NFA与DFA的主要的区别在于转换函数，DFA的转换函数是从S×∑到S上的一个单值映射，而NFA的转换函数是从S X∑到 ，即S的幂集的映射，而不是到S的映射，即一个状态可转换到的后继状态是一个状态集合(可能是空集)，而不是单个状态。另外，NFA有一个初态集，而DFA的初态是唯一的。2

有限自动理论研究有限自动机的功能、结构以及两者关系的数学理论称为有限自动机理论，有限自动机理论的基本内容包括逻辑网络、状态化简、状态分配、神经网络和有限识别器等。1

逻辑网络基本的逻辑元件按是否具有记忆功能，可以分为记忆元件(如触发器和延迟器等)和组合元件(如各种与、或、非门等)两类，把一些基本逻辑元件按一定要求连结起来，就组成逻辑网络，若把逻辑网络中进入记忆元件的输入线去掉后所得网络不再含有回路，则称这样的网络为合式网络，不含记忆元件的合式网络称组合网络，逻辑网络比组合网络复杂，在工程实现上，要求对于一个给定的有限自动机建立和实现此有限自动机的逻辑网络，已经证明任何合式网络的功能都可以用一个有限自动机来描述；任何一个有限自动机描述的功能也都可以用合式网络来实现。

状态化简对任何有限自动机都惟一(在同构意义下)存在一个状态数目最少的有限自动机与它等价，根据有限自动机理论，对给定的有限自动机，可有效地求出与之等价的最简形式的有限自动机。

状态分配要构造具有多个状态的网络，需要使用多个基本记忆元件，利用这些记忆元件的各种状态组合来表示不同的状态。一般地，不同的状态分配导致逻辑网络具有不同的复杂程度，如何选择较好的分配方案，使逻辑网络的构造尽可能地简单，是有限自动机研究的一个主要课题。

神经网络1943年，麦克卡洛克(Mcculloch)和皮特斯(Pitts,W.)提出的神经网络模型是有限自动机的一个实例，1951年，克林(Kleene,S.C.)在这种神经网络模型的基础上，提出了正则事件(正则语法)的概念，证明了正则事件是可以被神经网络或有限自动机表示的事件，而且神经网络或有限自动机可以表示的事件也一定是正则事件。

有限识别器在形式语言理论中,有限自动机通常作为语言的识别器来使用，作为识别器，有限自动机的输出可以被忽略，而由最后达到的状态去决定输入序列是否具有给定的性质，这种有限自动机也称为有限接收机，按其下步状态是否完全确定，有限识别器可分为确定型和非确定型两种，它们分别与确定型和非确定型有限自动机相对应，它们也都接受同一类语言,即正则语言。1