当前位置：首页 > news >正文

自动机，即有限状态机

news 文章来源：https://blog.csdn.net/m0_46638350/article/details/128998557 2024/11/7 3:39:35

文章目录

一、问题来源
二、题目描述
三、题解中的自动机
四、自动机学习
五、有限状态机的使用场景

一、问题来源

今天做力克题目的时候看到了字符串转换整数的一道算法题，其中又看到了题解中有自动机的概念，所以在这里对自动机做个笔记。题目链接

二、题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

示例 1：
输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步：“42”（当前没有读入字符，因为没有前导空格）
第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
第 3 步：“42”（读入 “42”）
解析得到整数 42 。
由于 “42” 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：
输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）
第 3 步：" -42"（读入 “42”）
解析得到整数 -42 。
由于 “-42” 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：
输入：s = “4193 with words”
输出：4193
解释：
第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）
第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
解析得到整数 4193 。
由于 “4193” 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

三、题解中的自动机

思路

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。

因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：

我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

算法
本题可以建立如下图所示的自动机：
在这里插入图片描述
接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可

四、自动机学习

根据上述，我们大概对自动机有一个初步的了解，接下来就详细地学习一下自动机
自动机是有限状态机(FSM)的数学模型。

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

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

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

自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现已被抽象化为如下的机器。时间是离散的（t=0，1，2……），在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。

五、有限状态机的使用场景

有限状态机的写法，逻辑清晰，表达力强，有利于封装事件。一个对象的状态越多、发生的事件越多，就越适合采用有限状态机的写法。