- 确定性有穷自动机 (Deterministic Finite Automaton, DFA)
- 定义
确定性有穷自动机是一个5元组[math]\displaystyle{ (Q,\Sigma,\delta,q_0,F) }[/math]，其中
1. Q是一个有穷集合，称为状态集 2. [math]\displaystyle{ \Sigma }[/math]是一个有穷集合，称为字母表 3. [math]\displaystyle{ \delta：Q×\Sigma \rightarrow Q }[/math]是状态转移函数 4. [math]\displaystyle{ q_0\in Q }[/math]是起始状态 5. [math]\displaystyle{ F\subseteq Q }[/math]是接受状态集
一台确定性有穷自动机有如上五个部分组成，介绍如下：
1. 它有一个状态集，表示它有的全部状态 2. 它有一个输入字母表，指明所有允许的输入符号 3. 它有一个根据一个输入字符从一个状态到另一个状态的规则 4. 它有一个起始状态，表示处理所起始的状态 5. 它有一个接受状态集，表示处理表达为接受的状态