=================
== Time Stream ==
=================
一个小学生

有限自动机

DFA 自动机

有限自动机知识学习。

有限自动机是一个识别器,对输入的字符做识别判断,输出的是接受或者拒绝。有限自动机分为:确定有限自动机(DFA)、非确定有限自动机(NFA)。

确定有限自动机(DFA)

DFA定义

DFA形式化定义是一个五元组:$M=(S, \Sigma, \delta, S_0, F)$,其中:

  • $S$ 称为状态集,是一个有限状态集合
  • $\Sigma$ 是字母表,是一个有限字母的集合
  • $\delta: S \times \Sigma \rightarrow S$ 是一个状态转移函数
  • $S_0 \in S$ 是起始状态
  • $F \subseteq S$ 是接受状态集

非确定有限自动机(NFA)

NFA形式化定义是一个五元组:$M=(S, \Sigma, f, S_0, F)$,其中:

  • $S$ 称为状态集,是一个有限状态集合
  • $\Sigma$ 是字母表,是一个有限字母的集合
  • f 是一个状态转移函数,为$f: S \times \Sigma^{*} \rightarrow 2^{S}$的部分映射
  • $S_0 \subseteq S$ 是非空初态集
  • $F \subseteq S$ 是终态集,可空