有穷自动机（有限状态机）是一个这样的机器：它只有有限个「状态」，并能按一定的规则，在一定的条件下唯一地从一个状态转移到其他一个或多个状态。世间许多事情本质都是状态机，比如「狼羊菜人过河问题」，就是不同的状态之间的转换：

确定的有穷自动机（DFA）

确定的有穷自动机是这样一种状态机：在每个状态下，对每个可能的输入，它都唯一地跳转到某一个状态（可以是其他状态，也可以是自己）。

形式化定义

DFA $A$ 定义为五元组

$$ A=(Q, \Sigma,\delta, q_0,F) $$

其中：

• $Q$ 是一个有穷的状态集合，即 $Q=\{q_0, q_1, \cdots, q_n\}$。
• $\Sigma$ 是字母表，即这台 DFA 能接受的输入字母集合，如 $\Sigma=\{0, 1\}$。
• $\delta$ 是一个函数「状态转移函数」，给出一个现态和一个输入字母，它能返回一个次态，即 $\delta(\text{现态}, \text{输入})=\text{次态}$。
  • 定义 $\hat\delta$ 为「扩展转移函数」，给出一个现态和一串输入字符串，它返回在这一串字符输入后 DFA 能跳转到的状态。
• $q_0$ 是 DFA 的初始状态，有 $q_0\in Q$。
• $F$ 是 DFA 的接受状态集合，当 DFA 进入这之中的状态时，表示目前的输入字符串能被 DFA 接受。有 $F\sube Q$。

直观表示

可以使用「转移图」和「转移表」来表示 DFA。

DFA 的语言——正则语言

能被 DFA $A$ 接受的字符串所组成的语言，称为 DFA 的语言，记作 $\mathbf{L}(A)=\{w|\hat\delta(q_0, w)\in F\}$。

DFA 的语言称作正则语言。