有限自动机例题

有限自动机（Finite State Machine）是计算机科学领域中的一种计算模型，用于描述自动化过程。自动机可以被看作是一个接受输入并给出输出的黑箱，其状态只取决于当前输入，在离散时间步长上依次执行。本文将从定义、类型、应用以及解题技巧等多个角度来介绍有限自动机。

定义

有限自动机由五元组（Q, Σ, δ, q0, F）组成，其中：

- Q：有限状态集合；

- Σ：有限输入字母表；

- δ：状态转移函数；

- q0：初始状态；

- F：终止状态集。

类型

有限自动机分为多种类型，包括：

- 非确定性有限自动机（Nondeterministic Finite Automaton，NFA）：对于某些状态，可能存在多种下一步状态选择，从而可能产生不同的输出序列。NFA可以被认为是一种多通道接收器，其每种选择方案可以视为一个通道。

- 确定性有限自动机（Deterministic Finite Automaton，DFA）：每个状态只存在唯一的下一步状态选择，因此输出序列是唯一的。DFA可以被认为是一种单通道接收器。

应用

有限自动机在模式匹配、语言识别、网站爬虫和编译器等方面得到广泛应用。在模式匹配中，有限自动机可以用于查找指定的字符串序列；在语言识别中，有限自动机可以用于识别特定语言的单词组成规则；在网站爬虫中，有限自动机可以用于爬取网页并提取所需信息；在编译器中，有限自动机可以用于将源代码转换为可执行代码。

解题技巧

在深入学习有限自动机原理的基础上，还需要掌握一些解题技巧。下面以LeetCode No. 10题为例来讲解如何使用有限自动机解题。

题目描述：给定一个字符串s和一个模式p，实现一个函数来寻找s中是否存在与p匹配的子字符串。？和 * 分别表示任意单个字符和零个或多个先前的元素。

解题思路：使用有限自动机进行模式匹配，将p模式转换为一个有限自动机。状态表示为当前子模式的结尾字符（或者空字符，表示还未匹配任何字符）。每个状态只与当前模式存在的字符有连接。有可能到达的下一个状态（即'*'所能够到达的所有状态）可以用DFS进行计算。

解题步骤：

- 构造有限自动机；

- 在有限自动机状态之间跳转，如果在‘*’位置跳转，继续输入，如果不匹配，就回到之前的状态，一直回溯到结果达成。

代码：

```

class Solution {

public:

bool isMatch(string s, string p) {

int n = s.size();

int m = p.size();

auto match = [&](int i, int j) -> bool {

if (i == 0) {

return false;

}

if (p[j - 1] == '.') {

return true;

}

return s[i - 1] == p[j - 1];

};

vector > f(n + 1, vector (m + 1));

f[0][0] = true;

for (int i = 0; i <= n; ++i) {

for (int j = 1; j <= m; ++j) {

if (p[j - 1] == '*') {

f[i][j] |= f[i][j - 2];

if (match(i, j - 1)) {

f[i][j] |= f[i - 1][j];

}

}

else {

if (match(i, j)) {

f[i][j] |= f[i - 1][j - 1];

}

}

}

}

return f[n][m];

}

};

```