从语音识别到编译器，有限状态自动机对于处理符号字符串非常有用。本教程将演示如何从头开始实现 DFA，以检查输入字符串是否遵循特定模式。

DFA 的快速回顾

DFA 由 5 个特征定义：

• 一组有限的状态
• 有限的符号字母表
• 起始状态
• 一组最终状态

将状态和符号映射到状态的转换函数

DFA 从起始状态开始。 DFA 读取字符串中的每个符号，并将当前状态和符号传递给转换函数。转换函数返回的状态成为 DFA 的新状态。读取所有符号后，如果 DFA 的状态是最终状态之一，则 DFA 接受该字符串，否则拒绝该字符串。

由于这个自动机是确定性的，我们不需要担心诸如 epsilon 转换或转换到可以在非确定性机器中找到的多种可能状态之类的事情。

在 Python 中定义 DFA

我们将从定义 DFA 类开始。此类的构造函数将包含上面列出的五个特性。

class DFA:    def __init__(self, states, alphabet, start, finals, transitions):        self.states = states        self.alphabet = alphabet        self.start = start        self.finals = finals        self.transitions = transitions

为了清楚起见，我们将为每个状态使用一个整数，为每个符号使用一个字符串，所以到目前为止我们有以下类型：

• states — int 列表
• 字母表 - str 列表
• 开始 - int
• finals — int 列表

接下来，我们需要表示我们的转换。 有多种方法可以做到这一点。 在本教程中，我们将使用字典来存储转换。 每个键将是一个包含当前状态和正在读取的符号的元组，相应的值将是 DFA 的下一个状态。

现在我们有了一个用于 DFA 的类，我们可以实例化一个示例。 我们将制作一个可以读取 As 和 B 字符串的 DFA，如果每两个 As 之间至少有两个 B，则接受它。

states = [0,1,2]alphabet = ["A","B"]start = 0finals = [0,1,2]transitions = {  (0,"A") : 1,    (0,"B") : 0,    (1,"B") : 2,    (2,"B") : 0,}dfa = DFA(states,alphabet,start,finals,transitions)

验证输入

为了让这个 DFA 验证字符串，我们在 DFA 类中定义了一个函数，该函数将字符串作为输入，读取每个符号，更新 DFA 的状态，然后检查最终状态的有效性。

该函数首先将当前状态设置为 DFA 的起始状态。 然后，它循环输入。 对于输入中的每个字母，它会查找当前状态和转换中的字母，并将新的当前状态设置为结果。 如果转换不存在，则函数返回 False。 循环完成后，它会检查当前状态是否是 DFA 的最终状态之一。

这是最终产品的样子：

class DFA:    def __init__(self, states, alphabet, start, finals, transitions):        self.states = states        self.alphabet = alphabet        self.start = start        self.finals = finals        self.transitions = transitions    def validate(self, string):        cur_state = self.start        for letter in string:            cur_state = self.transitions.get((cur_state,letter), -1)            if cur_state == -1:                return False        return cur_state in self.finals

浏览我们的示例

现在我们有了处理字符串的方法，我们可以使用我们的示例 DFA 进行尝试。让我们回顾一下运行 dfa.validate("ABBA") 时会发生什么：

1. cur_state 设置为 0，DFA 的起始状态
2. 程序开始循环遍历字母，以“A”开头
3. 在转换中查找 (0,A) 返回值 1，并将其存储在 cur_states
4. DFA 读取“B”，查找 (1,B)，并获得下一个状态 2
5. DFA 读取“B”，查找 (2,B)，并获得下一个状态 0
6. DFA 读取“A”，查找 (0,A)，并获得下一个状态 1
7. 由于循环后 cur_state 为 1 且 1 在 final 中，因此返回 True。

如果 DFA 尝试获取不存在的转换，则 transitions.get() 将返回 -1，立即导致 validate() 返回 False。

结论

我们已经讨论了如何从头开始实现确定性有限自动机类。我们已经演示了如何创建和使用 DFA 对象。现在您应该能够使用这些有限状态机的表达能力进行字符串处理。

关注七爪网，获取更多APP/小程序/网站源码资源！