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

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

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

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

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

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

有限自动机

有限自动机（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状态，然后再

次选择第一个匹配状态为E。

NFA和DFA的比较

尽管非确定性自动机很方便，不过，由于其能够采取任意选择，

因此它们较难实现和理解。FSA是一种较为常见和简单的有限状

态自动机类型，尽管它们不能像NFA那样追逐所有可能的路径，

但是在DFA的情况下，它们可以被准确理解和实现。

有限状态机在程序设计中有亮媚的应用，比如编译器，DNS，

并行计算等等。在编程中使用有限状态自动机可以带来多种好处。

最主要的是，他们提供了一种容易理解、容易调试的模型，而且

可以用移位运算器很容易地实现。此外，许多正式语法和模板匹

配系统使用有限状态自动机来执行模式匹配。

总结

自动机是一种抽象计算模型，尤其是在形式语言学中。有限自

动机是一种基本类型的自动机，由状态、转移函数、输入符号等

元素构成。非确定性自动机可以在任何可能的路径上处理输入，

由于其能够采取任意选择，因此它们较难实现和理解。本文着重

讲述了自动机的基本定义、应用及其逻辑，旨在展现自动机的重

要性和使用场景，同时也需要读者们注意到非确定性自动机存在

动态性及不确定性，应合理使用、使用时需注意。