词法分析： 由正规式构造确定的有穷自动机DFA


解题方法
1. 先由正规式构造转换系统
规则见下图：


2. 再由转换系统构造确定有穷自动机DFA
(1) 求 Ia
假定 I 是转换图状态集 K 一个子集，Ia 是 I 中状态经历 一条  a 弧(也可以是 b 弧，看具体题目要求，但必须经过一条)，同时可以跳过 a 弧前面和后面的若干 ε 弧，到达的状态集合。
(2) 子集法构造有穷自动机 DFA

画表，一共有 2*|∑|+2 列。第一列写 I ，表示状态子集。然后第二列至第 |∑|+1 列，写构造字母表（比如可以经过 a,b，那就第二列写 Ia，第三列写 Ib），然后第  |∑|+2 列，写上“状态”，最后  |∑| 列，写这些构造字母表（用作化简用，比如第五列写 a，第六列写 b）。
除去上面的各种列名称，下面开始的第一列第一行，写上初始状态 S 的状态子集 I。
针对后面紧跟的 |∑| 列，求相应的 I 子集（例如，Ia 列，就求状态子集 I 经过 求 Ia 后可以到达的状态集合，写入该列）。
当求完一行 Ia、Ib 后，把 Ia 和 Ib 中状态子集没有在左侧第一列 I 中出现过的，写入 I 列，重复上一步操作，直到全部出现在左侧第一列 I 中。
此时，第  |∑|+2 “状态” 列，从 0 开始标记，直到最后一行。
然后，再在最后的  |∑| 列中，根据相应的状态子集对应的数字标记，填写相应数字。
根据最后的 |∑|+1 列，画出 DFA 状态转换图。

3. DFA 化简
子集法构造的 DFA 不一定是最简的，往往会有冗余，此时需要化简。
(1) 将状态集划分成互不相交的子集（例如，开始把终态和非终态分开，分成两个子集）。
(2) 再对每个子集重复(1)进行划分，直到不能划分为止（所谓不能划分是指：该子集只有一个状态，或者该子集所有状态已不可再分）。
**注意点：**终态是这样来判断出来的：根据子集法中，最后得出的表，左边第一列，即 I 列中，包含 Z 终止状态的状态子集，都是终态（因为可以到达 Z）。
例题1
构造下列正规式相应的 DFA： (0 | 11*0)*
解：
1. 第一步：构造该正规式的转换系统



2. 第二步：由转换系统构造确定有穷自动机DFA
由上述转换系统可得状态转换集 K={S, 1, 2, 3, 4, Z}，状态子集转换矩阵如下表所示：




I
I0
I1
K
0      1




{S, 1, Z}
{1, Z}
{2, 3, 4}
0
1      2


{1, Z}
{1, Z}
{2, 3, 4}
1
1      2


{2, 3, 4}
{1, Z}
{3, 4}
2
1      3


{3, 4}
{1, Z}
{3, 4}
3
1      3


画出转换后的 DFA 状态转换图


3. 第三步：DFA 化简
由状态子集转换矩阵可知，状态 0 和 1 是等价的，而状态 2 和 3 是等价的，因此，合并等价状态之后只剩下 2 个状态，也即是最少状态的 DFA 。


例题2
将 (NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z})，构造相应的 DFA ，其中：M (X, 0) = {Z}     M (X, 1) = {X}     M (Y, 0) = {X, Y}  M (Y, 1) = Ф     M (Z, 0) = {X, Z}     M (Z, 1) = {Y}
解：
1. 第一步：构造该正规式的转换系统

2. 第二步：由转换系统构造确定有穷自动机DFA

3. DFA 化简
先化简，分为非终态集  {2, 4, 5, 0}  和 终态集 {6, 1, 3}，易于发现可划分为 {0,2}，{1}，{3,6}，{4}，{5}，其 DFA 如下所示

题目
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。
解题思路
下面是DFA：


注：

用一个vector内层使用map来保存状态之间的转移。
去掉首位空格后建立的自动机，加上空格也可以，只是状态会多出来一个（尾部多出一个识别空格的状态）。
小数点前面可以没有数字，对应状态8。
小数点后面也可以没有数字，对应状态3为接收状态和3后面直接跟e指数等。
接受状态：2、3、4、7。

代码
class Solution {
public:
    bool isNumber(string s) {
        if(s.size() == 0){
            return false;
        }
        //运用状态机进行判断
        //1.先去掉首尾空格
        int n = s.size();
        int start = 0;
        int end = n - 1;
        //全部是空格的字符串
        while(start < n && s[start] == ' '){
            ++start;
        }
        if(start == n){
            return false;
        }
        while(end >= 0 && s[end] == ' '){
            --end;
        }
        //然后用状态机进行判断，一共8个状态：
        int state = 0;
        //状态机判断
        judge(s, start, end, state);

        if(state == 2 || state == 3 || state == 4 || state == 7){
            return true;
        }
        return false;
    }
private:
    //状态机的9个状态，2、3、4、7是接收状态
    //0.初始状态
    //1.含有底数前符号+/-
    //2.小数点前数字
    //3.小数点
    //4.小数点后数字
    //5.e指数
    //6.e后面指数的符号
    //7.指数的数字  
    //8.小数点前没有数字
    vector<unordered_map<char, int>> myMap;

    void judge(string s, int start, int end, int &state){
        myMap = vector<unordered_map<char, int>>(9);
        myMap[0] = {{'+', 1}, {'-', 1}, {'d', 2}, {'.', 8}};    //注：小数点前没有数字也符合
        myMap[1] = {{'d', 2}, {'.', 8}};
        myMap[2] = {{'d', 2}, {'.', 3}, {'e', 5}};
        myMap[3] = {{'d', 4}, {'e', 5}};
        myMap[4] = {{'d', 4}, {'e', 5}};
        myMap[5] = {{'+', 6}, {'-', 6}, {'d', 7}};
        myMap[6] = {{'d', 7}};
        myMap[7] = {{'d', 7}};
        myMap[8] = {{'d', 4}};

        for(int i = start; i <= end; ++i){
            char c = s[i];
            if(c >= '0' && c <= '9'){   //数字
                c = 'd';
                if(myMap[state].count(c)){
                    state = myMap[state][c];
                }
                else{   //非法输入，不能进行状态转换，直接将state置为0
                    state = 0;  //0不是接收状态，置为0，然后返回
                    return;
                }
            }
            else{
                if(myMap[state].count(c)){
                    state = myMap[state][c];
                }
                else{   //非法输入，不能进行状态转换，直接将state置为0
                    state = 0;  //0不是接收状态，置为0，然后返回
                    return;
                }
            }
        }
    }
};

这种自动机在读任何输入序列后只能处在一个状态中
确定型，指的是：在每输入上，存在且仅存在一个状态，自动机可以从当前状态转移到这个状态。（此处对比非确定型，即可同时处在几个状态中）
NFA与DFA之间的唯一区别在于返回值的类型：在NFA的情况下，返回值是一个状态集合；而在DFA的情况下，返回值是单个状态。


确定型有穷自动机的定义
一个确定型有穷自动机包括：
1.一个有穷的状态集合，通常记作Q
2.一个有穷的输入符号集合，通常记作∑
      3.一个转移函数，以一个状态和一个输入符号作为变量，返回一个状态。转移函数通常记作δ
      4.一个初始状态q0，是Q中状态之一
      5.一个终结状态或接受状态的集合F
DFA五元组：A = （Q，∑，δ，q0，F）
   A = {有穷状态集合（条件集合），有穷输入符号集合，转移函数，初始状态，终结状态}


DFA处理串------DFA如何决定是否“接受”输入符号序列
DFA的‘语言’是这个DFA接受的所有的串的集合


例题1.形式化的规定一个DFA，接受所有仅在串中某个地方有01序列的0和1组成的串。
L：｛x01y | x和y是0和1的任意串｝
对于接受这个语言L的自动机A，可确定一下元组
输入字母表∑ = ｛0，1｝
 有穷状态集合Q，其中的一个状态为初始状态
自动机A需要明确：至此看到了什么样的输入。
1.是否已经看到01：如果是，就可接受后续输入的每一个序列，即从现在起只处在接受状态中
2.是否还没看到01，但上一个输入是0，如果现在看到1，那就看到01了。并且由此开始接受输入的所有序列
3.是否还没看到01，但上一个输入要么不存在（刚开始运行），要么上次看到的是1，在这种情况下，A直到先看到0然后理解看到1才接受；
（1）这三个条件每个都能用一个状态来表示。其中，条件3作为初始状态，用q0来表示。因为在刚开始去看是，需要看到一个0然后在看到一个1。但如果在q0状态下先看到一个1，那随后的状态应仍处在q0。即δ（q0，1）=
 q0
当，在q0状态下先看到0了，那就可以转移至条件2（状态2），此时的状态转移函数记为δ（q0，0）=
 q2 
    （2）现在处于状态2，从此刻出发。接下来如果看的的是0，那就相当于仍是处在状态2，即为δ（q2，0）= q2
接下来如果看到的是1，意味着现在已经看到01了，即可转移至条件1（状态1），此时的状态转移函数，即为δ（q2，1）= q1
    （3）现在处于状态1，此时已经看到01，意味着无论后续输入什么，都已处于成功的状态，所以此时的状态转移函数，即为（q1，0）= q1，
（q1，1）= q1    
  分析至此，确定了有穷状态集合Q = ｛q0，q1，q2｝
综上所述，对自动机A的完整描述是：A = （{q0，q1，q2}，{0，1}，δ，q0，{q1}）

前言
字母表∑1和∑2的乘积( product)：
∑1∑2 ={ab|a ∈∑1, b ∈ ∑2}
例： {0, 1} {a, b} ={0a, 0b, 1a, 1b}
字母表∑的n次幂( power)：长度为n的符号串构成的集合
∑0 ={ ε }

　　∑n =∑n-1 ∑ , n ≥
例： {0, 1}3 ={0, 1} {0, 1} {0, 1}={000, 001, 010, 011, 100, 101, 110, 111}
字母表的正闭包（positive closure）：长度正数的符号串构成的集合：
∑+ = ∑ ∪∑2 ∪∑3 ∪…
例：{a, b, c, d }+ = {a, b, c, d,aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}
字母表的克林闭包（Kleene closure）：任意符号串（长度可以为零）构成的集合：
∑* = ∑0 ∪∑+ = ∑0 ∪∑ ∪∑2 ∪∑3 ∪…
例：{a, b, c, d }* = {ε, a, b, c, d,aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}
一、有穷自动机
定义

有穷自动机 ( Finite Automata，FA )由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型
这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

Finite Automata的典型例子：

电梯控制装置
输入：顾客的乘梯需求（所要到达的层号）
状态：电梯所处的层数+运动方向
电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没有满足的所有服务请求

Finite Automata模型示意：



输入带(input tape)：用来存放输入符号串
读头(head )：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动
有穷控制器( finite control )：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态

FiniteAutomata的表示：

转换图 (Transition Graph)

- 结点：FA的状态

- 初始状态（开始状态）：只有一个，由start箭头指向

- 终止状态（接收状态）：可以有多个，用双圈表示

- 带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a



Finite Automata定义(接收)的语言：

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收
由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M （machine）)



最长子串匹配原则(Longest String Matching Principle )

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配



在到达某个终态之后，只要输入带上还有符号， DFA就继续前进，以便寻找尽可能长的匹配

二、有穷自动机的分类

确定的FA (Deterministic finite automata, DFA)
非确定的FA (Nondeterministic finite automata, NFA)

确定的有穷自动机DFA(Deterministic Finite Automata)
M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素
δ：将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。
s0：开始状态 (或初始状态)，s0∈S
F：接收状态（或终止状态）集合，F⊆ S

例如下图所展示的一个DFA


非确定的有穷自动机NFA(NonDeterministic Finite Automata)
M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素
δ：将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0：开始状态 (或初始状态)，s0∈S
F：接收状态（或终止状态）集合，F⊆ S

例如下图所展示的一个NFA


(DFA与NFA的区别在于：如上图用红色方框标出的位置，DFA的每一次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集，后面将使用子集法将NFA构造为DFA)。
3、DFA和NFA的等价性
①

对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D
对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

②

DFA和NFA可以识别相同的语言（如下图举例所示）


带有“ε-边”的NFA
M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入符号集合，即输入字母表。假设ε不是Σ中的元素
δ：将S×(Σ∪{ε})映射到2S的转换函数。s∈S, a∈Σ∪{ε}, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0：开始状态 (或初始状态)，s0∈S
F：接收状态（或终止状态）集合，F⊆ S



带有和不带有“ε-边”的NFA 的等价性

DFA的算法实现


输入：以文件结束符eof结尾的字符串x。DFA D 的开始状态s0，接收状态集 F，转换函数move。


输出：如果 D接收 x，则回答“yes”，否则回答“no”。


方法：将下述算法应用于输入串 x。


s = s0 ;
c = nextChar（）;
while（c! = eof ）｛ 
    s = move ( s , c ) ;
    c = nextChar ( ) ;
｝
if (s在F中) return“yes”;
else return “no”;



函数nextChar( )返回输入串x的下一个符号


函数move(s, c)表示从状态s出发，沿着标记为c的边所能到达的状态


三、从正则表达式到有穷自动机

根据RE 构造NFA

ε对应的NFA


字母表Σ中符号a对应的NFA




r = r1r2对应的NFA




r = r1|r2对应的NFA




r = (r1)*对应的NFA



例:r=(a|b)*abb 对应的NFA