浅谈DFA确定有限状态自动机

本文介绍确定有限状态自动机DFA的基本原理，并结合具体示例进行实践

基本原理

对于DFA确定有限状态自动机A而言，其通常包含以下几个元素：

1. 非空有限的状态集合 Q
2. 非空有限的输入集合 ∑
3. 转移函数 𝜹: Q x ∑ -> Q。其决定了当前状态在某输入的作用下自动进入的下一个状态。例如 𝜹(q,𝝈)=p，其中：p∈Q，q∈Q，𝝈∈∑
4. 初始状态 s∈Q
5. 可接受状态集合 F⊆Q。其表明当输入结束时，自动机所处状态为合法状态的集合

换言之一个DFA可以表述为A=(Q,∑,𝜹,s,F)。其基本工作流程：DFA从初始状态开始，每当从输入集合中读入一个输入元素时，DFA便根据转移函数自动转移至下一个状态。当输入完毕时，自动机的状态如果为可接受状态，则表示输入合法；反之即为非法。至此可以看出DFA能够处理的场景为：对于给定的输入字符串S，判断其是否满足条件P

实践

学习过程中要善于理论联系实际。故在介绍完DFA的基本原理后，现在我们来进行实践。这里以LeetCode的剑指Offer(第2版)题单中的第20题——表示数值的字符串为例

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）

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

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

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

• （可选）一个符号字符（’+’ 或 ‘-‘）
• 下述格式之一：
  1. 至少一位数字，后面跟着一个点 ‘.’
  2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
  3. 一个点 ‘.’ ，后面跟着至少一位数字

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

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

部分数值列举如下：
[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

对于本题而言，非常适合通过DFA解决。现在按照DFA的五元素依次进行分析。对于输入集合而言，可以看出其有效的输入字符只能是以下几种：

1. 空格
2. 数字
3. 符号位：+正号、-负号
4. 小数点
5. 指数符号：e、E

下一步，则可以根据处理到字符串的哪个部分作为自动机的状态。至此不难分析出，对于本题其状态集合为：

1. 起始空格
2. 数字的符号位
3. 整数部分
4. 左侧有整数的小数点
5. 左侧无整数的小数点
6. 小数部分
7. 指数符号
8. 指数的符号位
9. 指数部分的整数
10. 结束空格

不难看出，自动机的初始化状态为起始空格。同时可以看到当字符串全部输入结束时，如果自动机处于以下状态之一时，则该字符串显然是可以表示为数值的。换言之，下述状态即为本自动机的可接受状态

1. 整数部分
2. 左侧有整数的小数点
3. 小数部分
4. 指数部分的整数
5. 结束空格

现在根据状态集合、输入集合实际上不难分析出本自动机的转移函数。具体如下所示

至此，DFA的五个元素就已经完全具备了。这里给出Java下的实现

/**
 * DFA 确定有限状态自动机
 */
class Solution {
    /**
     * 状态转移规则, 当前状态 + 输入类型 -> 下一个状态
     * 第一层Map, key: 当前状态
     * 第二层Map, key: 输入类型; value: 下一个状态
     */
    private static Map<State, Map<InputType, State>> transferRule;

    /**
     * 定义状态转移规则
     */
    static{
        transferRule = new HashMap<>();

        Map<InputType, State> map = new HashMap<>();
        map.put( InputType.BLANK, State.START_BANK );
        map.put( InputType.SIGN, State.NUMBER_SIGN );
        map.put( InputType.NUMBER, State.INTEGER );
        map.put( InputType.DOT, State.DOT_WITHOUT_INTEGER );
        transferRule.put( State.START_BANK, map );

        map = new HashMap<>();
        map.put( InputType.NUMBER, State.INTEGER );
        map.put( InputType.DOT, State.DOT_WITHOUT_INTEGER );
        transferRule.put( State.NUMBER_SIGN, map );

        map = new HashMap<>();
        map.put( InputType.NUMBER, State.INTEGER );
        map.put( InputType.DOT, State.DOT_WITH_INTEGER );
        map.put( InputType.POWER, State.POWER_LOGO );
        map.put( InputType.BLANK, State.END_BLANK );
        transferRule.put( State.INTEGER, map );

        map = new HashMap<>();
        map.put( InputType.BLANK, State.END_BLANK );
        map.put( InputType.POWER, State.POWER_LOGO );
        map.put( InputType.NUMBER, State.FLOAT );
        transferRule.put( State.DOT_WITH_INTEGER, map );

        map = new HashMap<>();
        map.put( InputType.NUMBER, State.FLOAT );
        transferRule.put( State.DOT_WITHOUT_INTEGER, map );

        map = new HashMap<>();
        map.put( InputType.NUMBER, State.FLOAT );
        map.put( InputType.POWER, State.POWER_LOGO );
        map.put( InputType.BLANK, State.END_BLANK );
        transferRule.put( State.FLOAT, map );

        map = new HashMap<>();
        map.put( InputType.SIGN, State.POWER_SIGN );
        map.put( InputType.NUMBER, State.POWER_NUMBER );
        transferRule.put( State.POWER_LOGO, map );

        map = new HashMap<>();
        map.put( InputType.NUMBER, State.POWER_NUMBER );
        transferRule.put( State.POWER_SIGN, map );

        map = new HashMap<>();
        map.put( InputType.BLANK, State.END_BLANK );
        map.put( InputType.NUMBER, State.POWER_NUMBER );
        transferRule.put( State.POWER_NUMBER, map );

        map = new HashMap<>();
        map.put( InputType.BLANK, State.END_BLANK );
        transferRule.put( State.END_BLANK, map );
    }

    /**
     * 判断字符串是否表示数值
     * @param s
     * @return
     */
    public boolean isNumber(String s) {
        if( s==null || s.length()==0)  {
            return false;
        }

        char[] chars = s.toCharArray();
        // DFA的起始状态为 <起始空格>
        State state = State.START_BANK;
        for (char ch : chars) {
            // 根据字符计算输入类型
            InputType inputType = InputType.calcInputType(ch);
            // 根据当前状态获取下一步的状态转移规则
            Map<InputType, State> map = transferRule.get(state);
            // 根据当前状态的转移规则、输入类型计算出下一个状态
            State nextState = map.get(inputType);
            if( nextState==null ) {
                // 下一个状态为空, 说明相应的输入类型不合法
                return false;
            }
            // 更新当前状态
            state = nextState;
        }

        // 如果最终的状态为可接受的, 则返回true; 反之为false
        return state.isAccept();
    }
}

/**
 * 状态
 */
enum State {
    START_BANK("起始空格", false),
    NUMBER_SIGN("数字的符号位", false),
    INTEGER("整数部分", true),
    DOT_WITH_INTEGER("左侧有整数的小数点", true),
    DOT_WITHOUT_INTEGER("左侧无整数的小数点", false),
    FLOAT("小数部分", true),
    POWER_LOGO("指数符号", false),
    POWER_SIGN("指数的符号位", false),
    POWER_NUMBER("指数部分的整数", true),
    END_BLANK( "结束空格", true),
    ;

    /**
     * 状态名称
     */
    private String name;

    /**
     * 是否为接受状态
     * true: 接受状态
     * false: 非接受状态
     */
    private boolean accept;

    State(String name, boolean accept) {
        this.name = name;
        this.accept = accept;
    }

    public boolean isAccept() {
        return accept;
    }
}

/**
 * 输入类型
 */
enum InputType {
    OTHER("非法输入"),
    BLANK("空格"),
    NUMBER("数字"),
    SIGN("符号位"),
    DOT("小数点"),
    POWER("指数符号"),
    ;

    private String name;

    InputType(String name) {
        this.name = name;
    }

    /**
     * 根据字符计算输入类型
     * @param ch
     * @return
     */
    public static InputType calcInputType(char ch) {
        if ( ch==' ' ) {
            return BLANK;
        } else if( ch>='0' && ch<='9' ) {
            return NUMBER;
        } else if ( ch=='+' || ch=='-' ) {
            return SIGN;
        } else if ( ch=='.' ) {
            return DOT;
        } else if ( ch=='e' || ch=='E' ) {
            return POWER;
        }
        return OTHER;
    }
}