查看“有穷自动机”的源代码

== 确定性有穷自动机  (Deterministic Finite Automaton, DFA) ==

=== 定义 ===

确定性有穷自动机是一个5元组<math>(Q,\Sigma,\delta,q_0,F)</math>，其中

# Q是一个有穷集合，称为状态集
# <math>\Sigma</math>是一个有穷集合，称为字母表
# <math>\delta：Q×\Sigma \rightarrow Q</math>是状态转移函数
# <math>q_0\in Q</math>是起始状态
# <math>F\subseteq Q</math>是接受状态集

一台确定性有穷自动机有如上五个部分组成，介绍如下：

# 它有一个状态集，表示它有的全部状态
# 它有一个输入字母表，指明所有允许的输入符号
# 它有一个根据一个输入字符从一个状态到另一个状态的规则
# 它有一个起始状态，表示处理所起始的状态
# 它有一个接受状态集，表示处理表达为接受的状态

=== 用处 ===
主要对于输入的字符串判定是否该确定性有穷自动机所识别的语言，对此表示接受及不接受。

而如上的确定性有穷自动机是识别以0结尾的串，对于以0结尾的串<math>x \in \Sigma^*</math>，表示接受，反之不接受。

确定性有穷自动机可以用来定义语言也可用于识别语言。

=== 运算 ===
假如现在有个确定性有穷自动机<math>\mathcal M_1=(Q,\Sigma,\delta,q_0,F)</math>

<math>
\begin{alignat}{3}
Q=\{q_0,q_1\}\\
\Sigma=\{0,1\}\\
\delta=\begin{Bmatrix}
\delta(q_0,0)=q_1\\
\delta(q_0,1)=q_0\\
\delta(q_1,0)=q_1\\
\delta(q_1,1)=q_0
\end{Bmatrix}\\
F=\{q_1\}
\end{alignat}
</math>

假如对于上面的确定性有穷自动机<math>\mathcal M_1</math>，输入字符串<math>010</math>，此时从初始状态<math>q_0</math>开始，读入第一个字符<math>0</math>，因为<math>\delta(q_0,0)=q_1</math>，所以转移状态至<math>q_1</math>，继续读入下一个字符<math>1</math>，因为<math>\delta(q_1,1)=q_0</math>，所以转移状态至$q_0$，继续读入下一个字符<math>0</math>，因为<math>\delta(q_0,0)=1</math>所以转移状态至<math>q_1</math>，运算结束。因为最后停在状态<math>q_1</math>，因为<math>q_1 \in F</math>，所以确定性有穷自动机<math>\mathcal M_1</math>接受字符串<math>010</math>。