词法分析：有限自动机

字数统计: 4.4k字 | 阅读时长: 18分

2020-07-21

摘要: 有限自动机的原理与实现，若干例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们简要串讲一下词法分析中的有限自动机理论，然后解决力扣上的 4 道相关题目：

$0 词法分析和有限自动机

在编译原理中，一个程序语言的单词表大致如下：

基本字: for, while, int, return, const, ...
标识符: tmp, next, left, ...
常数: 3, 1.7, 'o', "abc", 1e9, 2.5e-7, ...
运算符: +, -, *, /, ^, ...
分界符: 空格，空行

是词法分析的对象，单词表里的所有单词构成了一个字符串的集合，这种集合称为正则集。词法分析要研究的是正则集。

正则集可以用正则表达式表示，它们是一一对应的。

词法分析器的功能就是输入源串，输出单词符号，这里的输出单词符号包含两部分：单词类别和单词自身的值，类别和值由单词表给定。

可以以状态转换图为工具手工设计词法分析器。

确定有限自动机 DFA 是状态转换图的形式化。

DFA 是一种自动机，可以用于描述状态转换图，容易做程序实现，且任何一个 DFA 的程序实现框架是一样的，差别仅在于状态转移矩阵(相当于邻接矩阵)。

伪代码如下：

// cur_state = 初态
// 获取下一字符 ch
string str = "";
while(statetrans[cur_state][ch] 有定义)
{
    str += ch;
    cur_state = statetrans[cur_state][ch];
    if(cur_state 是终态)
        return str;
    // 获取下一字符
}

但是 DFA 不容易做设计，给定一个语言的单词表试图画一个 DFA 识别这种语言的话，很困难。

但是幸运的是设计非确定有限自动机 NFA 识别某种语言相对比较容易，NFA 和 DFA 是等价的。DFA 是 NFA 的特例，任何 NFA 都有算法可以转化为 DFA，即子集法。

给定单词表，用 NFA 做设计还是嫌有些难，但是幸运的是 NFA 和正则表达式之间可以互相转化。而拿到语言的单词表后，写正则表达式是相对容易的。

通过 语言单词表 -> 正则表达式 -> NFA -> DFA 这条路线得到 DFA，之后，还有成熟算法可以将 DFA 化简，使得状态数量最少。每个步骤的是有算法的(算法本身就是等价性的构造性证明)，因此可以自动化地实现。

词法规则还可以用文法描述，正则文法和 NFA 之间可以互相转化。

因此最终结论：如果要研究一个语言的词法分析，拿到单词表后有两种选择

用正则表达式描述词法规则
用正则文法描述词法规则

这两种方法都可以得到 NFA, 进而得到 DFA，进而优化 DFA 使得状态数最少。

以上就是词法分析的整体逻辑，涉及到文法，正则表达式，有限自动机，概念之间的关系如上图，其中每个箭头都有证明，而证明过程是一种构造性证明，这种构造性证明就是概念间进行转化的算法。

证明过程和算法的细节需要参考编译原理词法分析部分。

力扣上有几道经典的有限自动机的题目，涉及到的方法是上述词法分析逻辑链条中 以状态转换图为工具手工设计词法分析器 这一块，

而 DFA 是状态转换图的形式化，因此就是拿到较简单的单词表后手工设计对应的 DFA，进而画出状态转换图，写出状态转移矩阵。

有限自动机的形式化定义

记 DFA $M = (S, \Sigma, f, S_{0}, F)$，其中：

$S$ 为状态集合，如果把 DFA 视为有向图，则 DFA 为图上的节点。
$\Sigma$ 为字符集，该自动机只能接受这些字符。
$f$ 为转移函数，接受两个参数，返回一个值，其中第一个参数和返回值都是状态集合中的状态，第二个参数是一个字符集中的一个字符。
$S_{0}$ 是起始状态。
$F$ 是终结状态集合。

比较常见的自动机有：Trie、KMP 算法、AC 自动机、后缀自动机、回文自动机、序列自动机。

$2 题目

65. 有效数字

有效数字（按顺序）可以分成以下几个部分：

一个小数或者整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：

至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字

部分有效数字列举如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”]

给你一个字符串 s ，如果 s 是一个有效数字，请返回 true 。

示例 1：
输入：s = “0”
输出：true

示例 2：
输入：s = “e”
输出：false

示例 3：
输入：s = “.”
输出：false

提示：

1 2	1 <= s.length <= 20 s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

算法1：自动机 (手工设计 DFA)

下面从词法分析的角度分析这道题：

字符集：

符号：+-
数字：0123456789
点：.
e：eE
空格： 
非法字符：所有其它字符

词汇表(词法规则)

前面可以有空格，后面可以有空格
最左边可以有+-
如果有小数点，小数点两边至少一边有数字就可以，
如果有 e/E，e/E 右边必须接数字，e接的数字可以有+-

按照 $1 的结论，拿到词汇表之后，可以写正则表达式或正则文法，自动化地得到 DFA；如果词汇表比较简单，手工设计DFA难度不大，也可以直接设计DFA。

方法1: 正则表达式

由词法规则写出正则表达式 "^\\s*[+-]?(\\.\\d+|\\d+\\.?\\d*)([eE][+-]?\\d+)?\\s*$"

class Solution_2 {
public:
    bool isNumber(string s) {
        regex reg("^\\s*[+-]?(\\.\\d+|\\d+\\.?\\d*)([eE][+-]?\\d+)?\\s*$");
        bool flag = regex_match(s, reg);
        return flag;
    }
};

方法2: 手工设计 DFA

因状态数比较少，可以手工设计 DFA：

记 DFA $M = (S, \Sigma, f, S_{0}, F)$

首先看状态集合 $S$

-1: 非法状态
0: 开始的空格,如” “
1: 到e前的正负号，如” +”
2: 到e前左侧无数字的小数点，如” +.”
3: 到e前未遇到小数点的整数，如” +1”
4: 到e前的小数，如” +1.e”
5: 到e，如” +1.1e”
6: 到e后的正负号，如” +1.1e”
7: 到e后的整数，如” +1.1e1”
8: 到最后的空格，如” +1.1e1 “

再看字母表 $\Sigma$

空格
+-
0123456789
.
e
非法字符

初始状态 $S_{0} = 0$

终结状态 $F = \{3, 4, 7, 8\}$

DFA 从状态 0 开始逐字符读字符串，在某字符处状态转移后，若所得状态非法，直接返回 false，否则继续读下一字符，直至字符串耗尽。

当字符串耗尽，若到达终止状态，则返回 true，否则返回 false

状态转移函数 $f$ 以状态转换图表示。

根据装谈转换图，列出状态转移矩阵

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

代码 (C++)

class Solution {
public:
    bool isNumber(string s) {
        if(s.empty()) return false;
        int n = s.size();

        int state = 0;
        vector<bool> finals({0, 0, 0, 1, 1, 0, 0, 1, 1}); // 合法的终止状态
        vector<vector<int> > transfer({
                {0,  1,  3,  2,  -1, -1},
                {-1, -1, 3,  2,  -1, -1},
                {-1, -1, 4,  -1, -1, -1},
                {8,  -1, 3,  4,  5,  -1},
                {8,  -1, 4,  -1, 5,  -1},
                {-1, 6,  7,  -1, -1, -1},
                {-1, -1, 7,  -1, -1, -1},
                {8,  -1, 7,  -1, -1, -1},
                {8,  -1, -1, -1, -1, -1},
                });

        for(int i = 0; i < n; ++i)
        {
            state = transfer[state][_make(s[i])];
            if(state < 0) return false;
        }
        return finals[state];
    }

private:
    int _make(const char& c)
    {
        switch(c)
        {
            case ' ': return 0;
            case '+': return 1;
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
            default: return _number(c);
        }
    }

    int _number(char c)
    {
        if(c >= '0' && c <= '9')
            return 2;
        else
            return 5;
    }
};

算法2：责任链模式

参考文章：责任链模式。

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。

示例 2:
输入：s = “aa”, p = “a“
输出：true
解释：因为 ‘‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：
输入：s = “ab”, p = “.“
输出：true
解释：”.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。

算法1: 动态规划

dp[i][j] := p[0..j-1] 是否能匹配 s[0..i-1]
dp[i][j] =
    dp[i - 1][j - 1] (p[j - 1] == . 或 p[j - 1] == s[i])
    false            (p[j - 1] != * 且 p[j - 1] != s[i])
    dp[i][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] 或 .))     (p[j - 1] == *)
初始化:
    dp[0..n][0..n] = false
    dp[0][0] = true
    dp[0][j] = dp[0][j - 2] (p[j - 1] == * 且 p[j - 2] != *)
迭代 i: 1..n; j: 1..m;
答案：dp[n][m]

考虑 dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] 或 .)) (p[j - 1] == *) 这个转移。

第一部分：dp[i][j - 2] 表示 s[0..i-1] 匹配 p[0..j-3]，即 p[j - 1] 的 * 匹配了 0 个 p[j - 2]
第二部分：当 p[j - 2] 即 p[j - 1] 的 * 前面的字母等于 s[i - 1] 或为 .，则 p[j - 1] 的 * 可以匹配 1 个 s[i - i]，继续看 s[i - 2]和 p[j - 1] 是否匹配，即 dp[i - 1][j]

精髓的地方是 dp[0][0] = 1 这个初始化。

代码 (C++)

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty() && p.empty()) return true;
        if(!s.empty() && p.empty()) return false;

        int n = s.size(), m = p.size();
        vector<vector<bool> > dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for(int j = 2; j <= m; j += 2)
            if(p[j - 1] == '*')
            {
                if(p[j - 2] != '*')
                    dp[0][j] = dp[0][j - 2];
                else
                    return false; // 剪枝
            }

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                if(p[j - 1] == s[i - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                {
                    if(p[j - 2] == '*')
                        return false; // 剪枝
                    dp[i][j] = dp[i][j - 2];
                    if(p[j - 2] == s[i - 1] || p[j - 2] == '.')
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        return dp[n][m];
    }
};

算法2：有限自动机

有限状态机根正则表达式是等价的。原因如下，以下是编译原理词法分析部分的结论。

正则表达式所匹配的所有字符串所构成的语言可以用有限自动机识别。正则集（正则表达式所匹配的所有字符串集合）是由右线性文法（3型文法）所产生的语言，两者是等价的。

DFA 需要根据 p 动态地构造，其中每个字符视为一个状态。这个实现还是挺复杂的，因为这里是要由正则表达式自动地生成有限自动机，而不是从简单的规则手工设计自动机。并且以下做法所得 DFA 一般是有冗余状态的，要优化状态数的化还涉及另外的算法，具体参考编译原理的词法分析部分。

状态转换图可以用邻接表的形式给出。节点定义如下：

struct StateNode
{
    int state; // 状态序号 0为开始状态 
    char val;  // 状态值 对应p字符串中的char值
    bool isR;  // 是否为可变长节点（即后面是否紧跟*字符）
    int firstNotRNextState; // 第一个后继非可变长节点状态序号
    StateNode(int _state, char _val, bool _isR) : state(_state), val(_val), isR(_isR) {}
};

具体过程看代码。分 3 步：

建 DFA 邻接表的节点，主要区分起始节点，终止节点，中间节点，并要做各个节点的第一个非可变长节点状态序号的赋值
建 DFA 邻接表的边，边权为输入字符值，例如 transfer[0][1] = ‘a’ 表示当输入为’a’时状态机可从0状态变到1状态, transfer[0][1] = -1 表示当前输入任意字符, 状态机可从0状态变到1状态以对应p串中的’.’字符
开始深度优先遍历回溯，逐个输入 s 串至自动机以判定是否能够成功达到结束节点

以下算法是正确的，但是很慢，因为这个 DFA 是可优化的。

代码 (C++)

class Solution {
public:
    //状态机节点结构体
    struct StateNode
    {
        int state; // 状态序号 0为开始状态 
        char val;  // 状态值 对应p字符串中的char值
        bool isR;  // 是否为可变长节点（即后面是否紧跟*字符）
        int firstNotRNextState; // 第一个后继非可变长节点状态序号
        StateNode(int _state, char _val, bool _isR) : state(_state), val(_val), isR(_isR) {}
    };

    vector<StateNode> stateNodeList; // 状态节点列表
    bool rlt = false; // 全局结果

    bool isMatch(string s, string p)
    {
        // 1. 构造状态机节点列表
        // 统计状态数
        int stateNum = 0;
        for (int i = 0; i < p.size(); i++)
        {
            if ('*' != p[i])
                stateNum++;
        }

        // 构造开始节点
        StateNode startNode = StateNode(0, -1, false);
        stateNodeList.push_back(startNode);
        int state = 1;

        // 构造中间状态节点
        for (int i = 0; i < p.size(); i++)
        {
            if ('*' == p[i])
                continue;
            bool isR;
            if (i + 1 < p.size() && '*' == p[i + 1])
                isR = true;
            else
                isR = false;
            StateNode node = StateNode(state++, p[i], isR);
            stateNodeList.push_back(node);
        }

        // 构造结束节点
        StateNode endNode = StateNode(state++, -1, false);
        stateNodeList.push_back(endNode);

        // 各个节点的第一个非可变长节点状态序号赋值
        for (int i = 0; i < stateNodeList.size(); i++)
        {
            StateNode *node = &stateNodeList[i];
            node -> firstNotRNextState = -1;
            for (int j = node->state + 1; j < stateNodeList.size(); j++)
            {
                StateNode bnode = stateNodeList[j];
                if(!bnode.isR)
                {
                    node -> firstNotRNextState = bnode.state;
                    break;
                }
            }
        }

        // 2. 根据状态机列表构造自动机对应图，权重为输入字符值
        // 例如 G[0][1]='a' 表示当输入为'a'时状态机可从0状态变到1状态
        // 特别标识G[0][1]=-1表示当前输入任意字符状态机可从0状态变到1状态以对应p串中的'.'字符
        vector<vector<int>> G(stateNum + 2, vector<int>(stateNum + 2));
        for (int i = 0; i < stateNodeList.size(); i++)
        {
            StateNode node = stateNodeList[i];
            if (node.isR)
            {
                //可变长节点自己形成环
                if ('.' == node.val)
                {
                    //处理任意输入都匹配的'.'字符
                    G[node.state][node.state] = -1;
                }
                else
                {
                    G[node.state][node.state] = node.val;
                }
            }

            // 非可变长节点与后继的所有可变长节点建立状态变化通路
            if (-1 != node.firstNotRNextState)
            {
                for (int i = node.state + 1; i <= node.firstNotRNextState; i++)
                {
                    StateNode middleNode = stateNodeList[i];
                    if ('.' == middleNode.val)
                    {   
                        //处理任意输入都匹配的'.'字符
                        G[node.state][middleNode.state] = -1;
                    }
                    else
                    {
                        G[node.state][middleNode.state] = middleNode.val;
                    }
                }
            }
        }
        // 3.开始深度优先遍历回溯，逐个输入 s 串至自动机以判定是否能够成功达到结束节点
        dfs(s, 0, 0, G);
        return rlt;
    }

    // 参数说明 index:s串输入下标 state：当前处理状态序号 G:自动机对应图
    void dfs(string s, int index, int state, vector<vector<int>> &G)
    {
        // 递归深度边界控制
        if (index > s.size())
            return;
        int stateNum = stateNodeList.size();
        StateNode curNode = stateNodeList[state];
        // 成功边界：s串扫描至末尾时，当前状态节点的第一个后继非可变长节点为结束节点
        if (stateNum - 1 == curNode.firstNotRNextState && index == s.size())
        {
            rlt = true;
            return;
        }

        char temp = s[index];
        // 遍历当前节点的所有后继子节点
        for (int i = state; i < stateNum; i++)
        {   
            // 值匹配或者'.'任意匹配成功
            if (G[state][i] == temp || G[state][i] == -1)
            {
                // 进入下一层处理s串中的下一个字符
                dfs(s, index + 1, i, G);
            }
        }
    }
};

8. 字符串转换整数 (atoi)

本题的相关内容可以参考文章 atoi的实现-模拟与有限自动机。

1262. 可被三整除的最大和

本题的相关内容可以参考文章同余类分解状态优化DP。

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法编译原理

词法分析：有限自动机

$0 词法分析和有限自动机

有限自动机的形式化定义

$2 题目

65. 有效数字

算法1：自动机 (手工设计 DFA)

代码 (C++)

算法2：责任链模式

10. 正则表达式匹配

算法1: 动态规划

代码 (C++)

算法2：有限自动机

代码 (C++)

8. 字符串转换整数 (atoi)

1262. 可被三整除的最大和

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1