跳到主要内容

有限自动机

阐述​

形式定义​

五元组 (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F)，其中

  • QQ 是有限状态集
  • Σ\Sigma 是有限字母表
  • δ:Q×Σ→Q\delta:Q\times\Sigma\to Q 是转换函数
  • q0∈Qq_0\in Q 是起始状态
  • F⊆QF\subseteq Q 是接受状态集

称有限自动机识别字符串 w=y1⋯ymw=y_1\cdots y_m，如果存在 r0,⋯ ,rm∈Qr_0,\cdots,r_m\in Q 使得

  1. r0=q0r_0=q_0
  2. ri+1=δ(ri,yi+1)r_{i+1}=\delta(r_i,y_{i+1})
  3. rm∈Fr_m\in F

阐释​

本质是对于内存非常有限的计算机的模型，其内存完全来自于系统处于哪一个状态。

如何设计有限自动机​

将自己放在机器的位置，思考自己如何用一种机械化的方式完成机器的任务。对于任何一个字符串，我们必须一个接一个地接收其中的字符，并在每个字符之后都马上给出该部分字符串是否符合的答案。

  1. 思考如何记住目前已看到字符串中的关键信息
  2. 将关键信息表示为几种可能性，为每个可能性关联一个状态
  3. 补充每读取一个字符将如何在这些状态中转换
  4. 标记初始状态和接受状态

实例​

性质​

相关内容​

有限自动机可以扩展为非确定性有限自动机，但它们的计算能力是等价的。

参考文献​