形式语言学中的自动机理论.pdfVIP

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

形式语言学中的自动机理论

自动机是形式语言学中重要的理论，定义为一种抽象的计算模

型，它可以接受一些输入并根据某些规则产生输出。自动机分为

有限自动机和非确定有限自动机。这些机器可以被用来描述很多

问题，比如编译器、网络协议、自然语言处理等等。

有限自动机

有限自动机（FSA）是一种基本类型的自动机，它包含有状态

集合、转移函数和一些输入符号。简单来说，FSA是一个小机器，

它从输入符号中接收数据，并按照一定规则转换状态，最终输出

结果。

一个FSA由下列五元组组成：

-状态集合Q：有限个状态的集合。

-输入字母表Sigma：有限个输入符号的集合。

-转移函数delta：状态和输入组成的二元组的集合。即，

delta(Q,Sigma)-Q

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

-初始状态q0：Q中的一个元素，即初始状态。

-接受状态F：Q中的元素的集合

一个FSA的工作方式是，接受一串输入x0,x1,x2,...,xn，开始时，

输入从q0开始。FSA的转移函数delta将当前状态和输入xk

作为参数并返回新状态，然后状态转换到下一状态，直到达到n。

如果当前状态是F中的成员之一，则认为接受输入。

下面是一个简单的例子，它说明了如何使用有限状态自动机来

匹配一个字符串：

设想我们需要找到以下字符串中所有的“at”，“rat”，“cat”，

“flat”：

我们可以设计一个FSA来自动匹配这些字符串，如下所示：

FSA中的状态表示为圆圈，箭头表示状态转换，lable表示接受

转换字符符号。

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

我们可以开始在字符串中找到我们正在寻找的字符串了。首先，

从起始状态S开始，看第一个字符是“c”。由于S的S-A转换无

“c”，我们将保持在状态S中，从而我们将继续看到下一个字符。

这次，下一个字符是“a”，该状态的S-A转换具有符号“a”，因此

我们可以按照其方向移动，继续到下一个字符。

接着，再看到一个“t”，这里的路径没有“t”，因此，我们将自动

机状态恢复到起始状态中。然后，跳过第一个单词，“fly”，并再

次开始找单词。我们会在“rat”单词中发现匹配项，最后找到“flat”

单词并结束查找过程。

非确定的有限自动机

有限自动机只能采取一种路径，一步步移动，并按照给定规则

处理每个符号。非确定性有限自动机（NFA）允许一次采取多个

路径而不是一个路径，这意味着它可以在任何可能的路径上处理

输入，而不必遵守某些规则。可以通过在状态之间添加ε转换来

维护这种选择。ε转换不消耗输入，而是只是改变状态。

来看如下所示为一个NFA：

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

同样地，我们可以看到一个简单的例子以说明如何使用非确定

性自动机来匹配字符串。

在NFA中，我们也可以从状态S开始，其次可以选择任何一

个状态，在状态A和状态B中选择其中一个去匹配输入。如果我

们遇到的字符不匹配，我们可以一次性进入C和D状态，然后再