3.1. 确定有限接受器¶
3.1.1. DFA：确定有限接受器¶
我们从最简单的机器开始：确定有限接受器 (DFA)。这台机器可以从左到右处理输入字符串（输入显示在一条纸带上）。它有一个控制单元（包含若干状态），并且规定了：当处于给定状态、当前纸带方格上为给定符号时，应该如何行动。我们唯一能"做"的就是在移到右边下一个字符之前改变状态。也就是说，接受器不会修改纸带上的内容。
这里的 确定的 一词有特定的含义：当 DFA 处于给定状态时，对任何给定的输入符号，它都只有一种可以做的事。这与 非确定的 机器形成对比，后者在处于给定状态、看到给定符号时，可能有多种可选的处理方式。我们稍后再讨论非确定自动机。
在处理完字符串的所有字符之后，DFA 可以回答"是"或"否"。例如，一台用于检查字符串是否为合法整数的 DFA，当输入为 6789 时应输出"是"。一台用于检查字符串是否为合法 C++ 变量名的 DFA，当输入为 SUM 时应输出"是"。
备注
在继续阅读之前先想一想：我们需要哪些信息来刻画/描述/定义一个给定的 DFA？我们希望信息足够多，以便能够"构建"这台机器，但也仅此而已。
将 DFA 定义为 \((Q, \Sigma, \delta, q_0, F)\) ，其中
\(Q\) 是状态的有限集合
\(\Sigma\) 是输入字母表（有限集合）
\(\delta: Q \times\Sigma \rightarrow Q\) 。一组形如 \((q_i, a) \rightarrow q_j\) 的转移，含义是：当处于状态 \(q_i\) 时，若看到字母 \(a\) ，就消耗掉它并转移到状态 \(q_j\) 。
\(q_0\) 是初始状态（ \(q_0 \in Q\) ）
\(F \subseteq Q\) 是终态集合
我们的解释是：如果 DFA 在处理某个输入字符串结束时处于终态，就认为它对该字符串输出"是"；如果在处理结束时不在终态，就认为它输出"否"。
DFA 是一台能力不大的简单机器。我们会看到，关于字符串，它有许多问题无法回答。例如，它无法判断 \(((9+5)+a)\) 是否为合法的算术表达式。
3.1.1.1. 示例¶
下面是一个接受偶二进制数的 DFA 的图形化展示。
我们可以为这些状态赋予语义：当已经处理的数字构成奇数时，机器处于状态 \(q_0\) ；当已经处理的数字构成偶数时，机器处于状态 \(q_1\) 。当然，我们这样去理解它们只是为了帮助自己理解所发生的事情。说这些状态"意味着"什么，并不会改变机器的实际行为。
备注
此时，你应该尝试在 OpenFLAP 中构建这台机器。
形式化定义：
\(M = (Q, \Sigma, \delta, q0, F) =\)
\((\{q0,q1\}, \{0,1\}, \delta, q0, \{q1\})\)
下面是 \(\delta\) 的表格形式：
备注
看看你能不能不看答案就写出这张表。
一次移动的示例：\(\delta(q0, 1) = q0\)
3.1.1.2. DFA 的算法：¶
现在让我们看看这台机器如何接受/拒绝一些字符串。
3.1.1.3. 定义¶
\({\delta}^{*}(q,\lambda)=q\)
你没有去任何地方，你仍在状态 \(q\)
\({\delta}^{*}(q,wa)={\delta}({\delta}^{*}(q,w),a)\)
先对 \(w\) （某个字符串）整体应用 \(\delta\) ，然后再应用到 \(a\)
DFA \(M = (Q, \Sigma, \delta, q_0, F)\) 接受的语言是 \(\Sigma\) 上所有被 \(M\) 接受的字符串的集合。形式化地，
\[L(M) = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\in F\}\]备注
画一幅图：从 q0 出发的弧……通向某个终态；任何通向终态的路径都对应一条被接受的字符串。
这就是 DFA M 所接受的语言。所有由字母表元素构成的字符串，只要从 q0 开始处理完 w 中的所有符号后到达一个终态（接受态），就属于该语言。
不被接受的字符串集合：
\[\overline{L(M)} = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\not\in F\}\]
3.1.1.4. 陷阱状态¶
示例：考虑语言 \(L(M) = \{b^na | n > 0\}\)
备注
这是什么语言？答案：一个或多个 "b" 后面跟着一个 "a"。
所以，下面是一种画法：
备注
问题：我们需要状态 \(q_0\) 吗？
答案：需要。这是为了强制至少有一个 "b"。
注意，严格来说这是不完整的，因为这里有一些转移没有画出来。其思想是：如果我们能够到达一个接受状态，那么该字符串就被接受。但如果发生了图中未画出的转移（或者最终到达了接受状态以外的地方），那么该字符串就不被接受。
为了完整起见，我们可以添加一个或多个"陷阱"状态，并补上所有"额外"的转移。如下所示。
注意，陷阱状态并没有什么"特殊"之处。
给状态起有含义的名字是个好主意！
示例：\(L = \{ w \in \Sigma^* | w\) 含偶数个 a 且含偶数个 b。
备注
其他可以考虑的示例：可以为实数、整数、变量名（取决于规则）等创建 DFA。
示例：创建一个接受偶二进制数且含偶数个 1 的 DFA。
确定性指的是：当机器处于给定状态并看到给定字符时，只能有一种做法。
3.1.1.5. 概念：DFA 的能力¶
给定的 DFA 可以接受一个字符串集合（语言也不过如此）。所有可能的 DFA 构成一类机器。对于某一类型（某种）有限自动机，该类有限自动机所接受的语言集合称为一个 语言族 。因此，DFA 定义了它们所接受的一个语言族。一种语言是 正则 的，当且仅当存在一个 DFA \(M\) 使得 \(L = L(M)\) 。
