有穷自动机

确定性有穷自动机 (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. 它有一个接受状态集，表示处理表达为接受的状态