1. DFA：确定的有穷接受器¶
1.1. DFA 简介¶
我们先从最简单的机器开始： 确定的有穷接受器 （ DFA ）。这台机器可以自左向右处理输入串（输入显示在一条纸带上）。机器有一个控制单元（其中包含若干状态），它规定了：当机器处于某个给定状态、看到当前纸带方格上的某个给定符号时，应该采取什么行为。但机器真正能做的，只是在移动到右侧下一个符号之前改变状态。也就是说，接受器既不能修改纸带上的内容，也不能决定控制单元移动到何处。
这里的 确定的 一词具有特殊含义： 当 DFA 处于某个给定状态时，对任何给定的输入符号，它都只有一种做法。这与 非确定的 机器形成对比，后者在处于给定状态、看到给定符号时，可能有多种继续处理的选择。我们稍后再讨论非确定的自动机。
在处理完串中的各个符号之后，DFA 既可以"接受"该串，也可以"拒绝"该串。例如，一台用来判断串是否为合法整数的 DFA，当输入为 6789 时应接受，而当输入为 67a89 或 67.89 时应拒绝。一台用来判断串是否为合法 C++ 变量名的 DFA，当输入为 SUM 时应接受，而当输入为 1SUM 时应拒绝。
1.2. 一些示例¶
下面给出 DFA 处理一个串的算法。
下面是对一个简单输入的详细追踪。
现在来看看这台机器如何接受或拒绝某些串。
接下来是一个练习，让你练习使用 DFA 机器编辑器来构造机器。你不必太费心思考需要构造什么机器，只需把我们已经用过的那台机器重新搭出来即可。不过，完成这个练习会让你熟悉机器编辑器——这本书里你会经常见到它！
1.3. 进阶概念¶
1.4. DFA 的局限¶
一个给定的 DFA 可以接受一个串的集合，而串的集合就是一种语言。因此，DFA \(M\) 接受某种语言 \(L\) ，记作 \(L(M)\) 。
现在我们把思路再推进一步，考虑所有可能的 DFA。每个 DFA 都接受一种语言，所以所有 DFA 合在一起，可以接受某一族语言。这样的 语言族 于是由所有 DFA 共同定义。我们给这个特别的族取一个名字： 一种语言是 正则 的，当且仅当存在一个 DFA \(M\) 使得 \(L = L(M)\) 。至于我们为什么用"正则"来称呼这个族，后面再解释。现在，这仅仅是一个没有任何其他背景的定义。
由此引出的一个重要问题是： 是否存在 DFA 无法接受的语言？也就是说，是否存在不是正则的语言？不必让你一直猜下去，答案是肯定的。我们后面会证明这一点，然后介绍更强大的机器，它们可以接受范围更大的语言族。 .. odsascript:: DataStructures/FLA/FA.js .. odsascript:: AV/VisFormalLang/FA/DFAExampleCON.js .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/FA/DFAintroFS.js .. odsascript:: AV/VisFormalLang/FA/MachineTraceCON.js .. odsascript:: AV/VisFormalLang/FA/TraceEvenBinaryDFACON.js .. odsascript:: AV/PIFLA/FA/DFAadvancedFS.js
