有限状态自动机

[TOC]

定义——有限自动机

有限状态机（Finite-state machine, FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
有限状态机可以将复杂的逻辑简化为有限个稳定状态，在稳定状态中判断事件。其中有限不是指有限次处理，而是有限个稳定状态。

有限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。

在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。

有限状态机在日常中也随处可见:

红绿灯控制系统：主干道、支干道的黄灯、红灯、绿灯交替显示；
地铁入口的门禁闸机：只有被闸机接受的刷卡行为，闸机才会将关闭状态变为开启状态；
自动售卖机，只有投入合适的硬币，售卖机才会吐出相应的产品；
密码箱，只有输入正确的密码序列，密码箱才会变为开启状态。

状态机的要素
状态机的本质是有向图：包括节点和路径。

节点表示状态，路径表示状态迁移。

大多状态机在路径上会增加一些附加信息来表明状态迁移的细节：条件 / 动作。前者表示引起状态迁移的事件，后者表示与该状态迁移相关联的动作。

比如：地铁入口的门禁闸机，在用户刷卡后，如果接受，则闸机会打开闸门。这里的“用户刷卡”就是“条件”，“闸机会打开闸门”就是动作。

状态机可归纳为6个要素，即活跃状态（现态）、输入事件（条件）、输出事件（动作）、次态、初始和终止状态。“活跃状态”和“条件”是因，“动作”和“次态”是果。详解如下：

活跃状态，也叫现态：是指当前所处的状态。任何时候，只有一个状态能够成为活跃状态；
输入事件：又称为“条件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移；
输出事件：又称为“动作”，条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态；
次态：条件满足后要迁往的新状态。“次态”是相对于“活跃状态”而言的，“次态”一旦被激活，就转变成新的“活跃状态”了；
初始状态：即没有状态转入的状态。只有一个初始状态
终止状态：即没有状态转出的状态。只有一个终止状态

可以用 迁移状态表 表示整个过程，如下表：

活跃状态 \ 输入/输出	触发条件1/[执行动作1]	触发条件2/[执行动作2]	…
初始状态	中间状态1	中间状态2	中间状态…
中间状态1	中间状态x	中间状态x	中间状态…
中间状态2	中间状态x	中间状态x	中间状态…
中间状态…	中间状态x	中间状态x	中间状态…

有限状态机分类
主要有 接收器（acceptors） 和 转换器（transducers） 两种。转换器（transducers）依据状态和输入的关系，又分为两种：moore 状态机和 mealy 状态机。

接收器（acceptors）
接收器是指产生一个二值的输出，指示接收的输入是否能被接受。比如地铁入口的门禁闸机，在用户刷卡后决定是否打开闸门放行
transducers(转换器)
转换器（moore 状态机和 mealy 状态机）一般输出会受输入序列顺序影响，mealy 状态机还会受当前状态影响。我们一般看到的状态机大部分是 mealy 状态机。

力扣8.字符串转换整数 (atoi)官方代码参考

class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

参考

编程——有限自动机 - leancode的文章 - 知乎
 leetcode8.字符串转换整数 (atoi)