有限状态自动机

本文最后更新于 2025年3月27日 下午


知识前置

图灵机

一个设想中的机器,由图灵于1936年提出。
详见百度百科

图论

自己学去。


定义

自动机是一个对信号序列进行判定的数学模型,也就是给一个状态能自己转移到下一个状态并进行运算的机器。


构成

:状态集,表示自动机里的每个状态,即图中的点。
:字符集。
:可接受状态集,即结束状态的结点。
:初始状态。
:转移函数,

自动机从初始状态按转移函数转化,跑一定次数到答案状态,在可接受状态集内的即为答案。


实例

下面是一个判断二进制数奇偶的自动机,其中


在这个自动机中,读入一个二进制数,按照自动机进行操作,可以通过最终状态判断奇偶。


有限状态自动机
https://preview.algo-x.cn/articles/Deterministic-Finite-Automaton/
作者
Taoran
发布于
2024年4月12日
更新于
2025年3月27日
许可协议