基础知识

自动机是什么?

发布时间:2013-07-04 00:00:00

自动机

FSM,我们在日常生活、工作中都经常用到,但不知道大家对“自动机”是否知道呢?本文收集整理了一些资料,希望本文能对各位读者有比较大的参考价值。

概念

定义

自动机是有限状态机(FSM)的数学模型。

自动机
自动机
名词解释

FSM 是给定符号输入,依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。在常见的 FSM 的“Mealy”变体中,这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。

逐个读取输入中的符号,直到被完全耗尽(把它当作有一个字写在其上的磁带,通过自动机的读磁头来读取它;磁头在磁带上前行移动,一次读一个符号)。一旦输入被耗尽,自动机被称为“停止”了。

依赖自动机停止时的状态,称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”,则自动机“接受”了这个字。在另一方面,如果它停止于“拒绝状态”,则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。

自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现在已被抽象化为如下的机器。时间是离散的(t=0,1,2……),在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。作为自动机的例子可以举出由McCulloch-pitts的神经模型组合所得到的神经网络模型、数字计算机等。

注意事项

注意,自动机一般不必须有有限数目甚至可数个状态。比如,量子有限自动机有不可数无限个状态,因为所有可能状态的集合是在复投影空间中所有点的集合。所以,量子有限自动机和有限状态机一样,都是更一般想法拓扑自动机的特殊情况,它的状态的集合是拓扑空间,而状态转移函数取自在这个空间上的所有可能函数。拓扑自动机经常叫做 M-自动机,简单是半自动机加上接受状态集合的补充,这里的集合交集确定初始状态是被接受还是被拒绝。
一般的说,自动机不需要严格的接受或拒绝一个输入;它可以按某个在零和一之间的概率接受它。还是用量子有限自动机作为展示例子,它只按某个概率接受输入。这个想法也是更一般情况几何自动机或度量自动机的特殊情况,它的状态的集合是度量空间,一个语言被这个自动机接受如果在初始点和接受状态的集合之间的距离关于这个度量是足够的小。自动机广泛应用于工业生产上。

形式描述

对信号序列进行逻辑处理的装置。在自动控制领域内,是指离散数字系统的动态数学模型,可定义为一种逻辑结构,一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中,分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型,用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器,用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型,用来研究神经生理活动和思维规律,探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型,研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数,研究各种算法。现代自动机的一个重要特点是能与外界交换信息,并根据交换得来的信息改变自己的动作,即改变自己的功能,甚至改变自己的结构,以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。

自动机与一般机器的重要区别在于自动机具有固定的内在状态,即具有记忆能力和识别判断能力或决策能力,这正是现代信息处理系统的共同特点。因此,自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类,也可按其抽象结构和联结方式分类。主要有:有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。

术语

自动机有如下基本概念:

符号

有某种意义或在这个机器上有效的任意数据(datum)。符号有时就叫做“字母”。

字

通过一些符号串接而形成的有限字符串。

字母表

符号的有限集合。字母表经常指示为 Σ,它是在字母表中所有字母的集合。

语言

字的集合,由给定字母表中的符号形成。可以是也可以不是无限的。

Kleene闭包

一个语言可以被认为是所有可能字的子集。所有可能字的集合可以被认为是所有可能的字符串串接的集合。形式上说,所有可能字符串的集合叫做自由幺半群。它被指示为 Σ ,上标 * 被称为Kleene星号。

形式描述

自动机可以表示为5-元组,这里的:

Q 是状态的非空有穷集合。

∑ 是符号的有限集合,我们称为这个自动机接受的语言的字母表。 输入字符串都是∑上的字符串

δ 是状态转移函数,就是(右2)。

(对于非确定自动机,空串是允许的输入)。

q0 是开始状态,就是说自动机在还未处理输入的时候的状态(明显的 q0∈ Q)。

F 是终止状态集合,也叫做接受状态的 Q 中的状态的集合(就是 F⊆Q)。

分类

下面是三类有限自动机

确定有限自动机(DFA)

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)

自动机的状态对字母表中的每个符号可以有也可以没有转移,对一个符号甚至可以有多个转移。自动机接受一个字,如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的,自动机因此不知道如何继续读取输入,则拒绝这个字。

有ε转移的非确定有限自动机(FND-ε或ε-NFA)

除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外,它们可以做根本不关于符号的跳转。就是说,如果一个状态有标记著 ε 的转移,则 NFA 可以处在 ε-转移可到达的任何状态中,直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。
尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。

扩展

上述自动机接受的语言家族被称为正规语言(Regular Expression)。更强力的自动机可以接受更复杂的语言。比如:

下推自动机(PDA)

这种机器等同于 DFA (或 NFA),除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号,并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。

线性有界自动机(LBA)

LBA 是有限制的图灵机;不使用无限磁带,它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。
自动机
自动机

图灵机

它们是最强力的电脑器。它们拥有磁带形式的无限内存,和可以读取和变更磁带的磁头,它可在磁带上向任何方向移动。图灵机等价于演算法,是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。

最小化

根据 Myhill-Nerode定理,在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的演算法(时间开销是O(n2)的)构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。

能力判定

确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质,许多为其他自动机(下推自动机或图灵机)不能判定的问题,在有限状态自动机的情形下,都可以得到判定,并且存在有效的演算法。

对一个确定有限状态自动机,下述判定问题都可以判定,并且存在有效的演算法。

该自动机识别的语言是否为空集。

该自动机识别的语言是否为有限集。

该自动机是否与另一个确定有限状态自动机识别同一个的语言。

综上所述,本文已为讲解自动机,相信大家对自动机的认识越来越深入,希望本文能对各位读者有比较大的参考价值。

浏览过本文<自动机是什么?>的人也浏览了

柴油发电机故障解决

http://baike.cntronics.com/abc/5259

什么是交流发电机?

http://baike.cntronics.com/abc/5312


柴油发电机

http://baike.cntronics.com/abc/5254

要采购标记么,点这里了解一下价格!

为您推荐

意法半导体升级 ST87M01 NB‑IoT 模块,新增 SoftSIM、SGP.32 工厂配置与 Zephyr 生态支持 业界新闻

意法半导体升级 ST87M01 NB‑IoT 模块,新增 SoftSIM、SGP.32 工厂配置与 Zephyr 生态支持

意法半导体宣布为 ST87M01 工业 NB‑IoT 模块新增多项软件能力:集成 Onomondo SoftSIM 软件 SIM 方案、支持 SGP.32 标准工厂端预置 SIM 配置文件,同时发布 Zephyr 操作系统驱动。SoftSIM 无需实体 SIM 器件,可降低生产成本与设备功耗;依托 SGP.32,厂商可在产线直接写入运营商配置,统一工厂预置与后期远程管理。Zephyr 驱动支持 MQTT、CoAP、GNSS 定位等功能,降低开发者集成难度。该模块将在 Enlit Europe、electronica 2026 展会现场进行功能演示,面向表计、资产追踪等空间受限的大规模物联网场景。

AI&loT 通信广电 电源管理 电机驱动 ST(意法半导体)

东芝推出 TLX9909 光伏输出型光耦,可外部调节关断时间面向车载 SSR 应用 新品速递

东芝推出 TLX9909 光伏输出型光耦,可外部调节关断时间面向车载 SSR 应用

东芝电子元件及存储装置株式会社发布车载光伏输出型光耦 TLX9909 并开启批量出货。该器件符合 AEC‑Q101 车载标准,最小开路电压可达 13.5V,无需隔离侧电源与电荷泵电路;可借助外部栅极放电电路灵活调节关断时间,扩大高压功率 MOSFET 适配范围。搭配外置 MOSFET 可搭建高压大电流固态继电器 SSR,适用于电池管理系统 BMS、车载充电器 OBC、车载逆变器等场景,与 TLX9910 形成产品组合,方便工程师根据元器件数量、设计自由度选型。

汽车电子 能源电路 电源管理 光电显示 继电器 TOSHIBA(东芝)

Skyworks 推出 SKY4680x 多核车载音频 DSP,单核‑三核覆盖入门至高端整车平台 新品速递

Skyworks 推出 SKY4680x 多核车载音频 DSP,单核‑三核覆盖入门至高端整车平台

Skyworks(思佳讯)正式发布 SKY4680x 车载音频 DSP 系列,包含单核、双核、三核多种配置,覆盖从入门级到高端车型。该系列基于 Cadence HiFi 5 内核,三核版本总算力超 1.2GHz,集成 8MB 带 ECC 的 SRAM,多数场景无需外接 DRAM,可支持最高 64 路音频通道。器件支持自研算法、第三方音频 IP 以及边缘 AI 音频应用,搭配图形化音频开发环境与 SDK,帮助车企与 Tier1 实现跨车型软件复用,平衡座舱音频性能与 BOM 成本。目前工程样片与评估板已开放申请。

汽车电子 互联技术 处理器 SKYWORKS

MathWorks 取得 TÜV 南德认证扩展,智能体 AI 融入 ISO 26262 汽车功能安全开发流程 业界新闻

MathWorks 取得 TÜV 南德认证扩展,智能体 AI 融入 ISO 26262 汽车功能安全开发流程

MathWorks 宣布扩展 MATLAB、Simulink 等工具的 TÜV 南德认证范围,新增依据 ISO 26262 制定的 AI 工具分类指南,成为首家为功能安全场景下 AI 辅助工程工作流提供评估指南的工具供应商。借助 Simulink Agentic Toolkit 与 Polyspace Agentic Toolkit,可将 AI 智能体嵌入基于模型的完整开发链路,完成模型搭建、评审、测试生成、代码缺陷检测等工作。方案基于 Model Context Protocol(MCP),兼容 GitHub Copilot、Gemini CLI、Claude Code 等主流 AI 平台,在引入 AI 提效的同时,保障汽车安全关键项目所需的可审计、可追溯能力。

汽车电子 EMC安规 测试测量 MathWorks

Ceva NeuPro‑Nano NPU 实现首次量产,Mobilint REGULUS 边缘 AI SoC 采用 Ceva AI IP 新品速递

Ceva NeuPro‑Nano NPU 实现首次量产,Mobilint REGULUS 边缘 AI SoC 采用 Ceva AI IP

随着物理 AI 发展,AI 算力持续向功耗受限的边缘终端下沉。智能边缘 IP 厂商 Ceva 宣布,Mobilint 的 REGULUS 边缘 AI SoC 采用 Ceva SensPro™ AI DSP 以及 NeuPro‑Nano™ NPU,这也是 NeuPro NPU 系列产品的首次量产落地。REGULUS 在低于 3W 功耗下可实现 10TOPS AI 算力,支持最高 8GB 内存;采用感知 DSP 与神经网络 NPU 多引擎分工架构,面向机器人、无人机、机器视觉、智能摄像头等场景。基于该芯片的 MLD‑R1 AI USB 加速器已经正式出货,兼容主流 AI 开发框架,助力物理 AI 设备商用化。

安防监控 电源管理 互联技术 SoC CEVA

特别推荐

更多

行业动态

更多

技术应用

更多

选型替代

更多

产品信息

更多

热门搜索

更多

欢迎登录

没有账号,

账号注册

注册成功!

3S后自动为你跳转登陆