时间戳

首页 > 技术文章 > DFA——有限自动机

DFA——有限自动机

SsoZhNO-1 2020-10-15 17:10 原文

有限状态机

有限自动机是计算机专业编译原理这门课中的，我一个非科班出生的当然是没有学过的。不过我再数电中学过时序电路的状态转移，我觉得他们是一个东西，说实话，这些图画过不少，但是实现代码还从来没有写过。这次遇到leetcode08_atoi可以专门系统学习一下如何将状态机写成代码。
有限状态机：限状态机，（英语：Finite-state machine, FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。FSM（有限状态机）可以使用状态转移图来表示。此外可以使用多种类型的状态转移表。下面展示最常见的表示：当前状态（B）和条件（Y）的组合指示出下一个状态（C）。完整的动作信息可以只使用脚注来增加。包括完整动作信息的FSM定义可以使用状态表。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。

另外，在设计模式中，行为型模式有一类为状态模式(State pattern),状态模式接近于有限状态机的概念，状态模式可以解释为策略模式，它能够通过调用模式接口中定义的方法来切换策略。状态模式允许对象在内部状态发生改变时改变它的行为，对象看起来好像修改了它的类。

我个人认为主要是用来解决代码中包含大量与对象状态有关的条件语句【else-if】的情况，其解决方法是通过将各种具体的状态类抽象出来。

参考：

https://zh.wikipedia.org/wiki/有限状态机

https://zhuanlan.zhihu.com/p/46347732

https://juejin.im/post/6844903455492931598

相关习题：leetcode08 leetcode393 leetcode65

从画状态转移图到写成代码

以leetcode08_为例：

leetcode08_atoi题目描述：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231)

画出状态转移图：

写出状态转移表：

* 得到状态图后，转化为状态表：
*          ' '       +/-     num     other
* start    start   signed   number    end
* signed   end      end     number    end
* number   end      end     number    end
* end      end      end      end      end

创建一个内部类，然后使用map<String,String[]>存储状态转移表中的每个状态，创建两个方法分表叫get, getCol来获取当前状态。使用for循环遍历字符串来使得状态转移，具体代码如下：

public class leetcode08_myAtoi {
    public int myAtoi(String s) {
        Automation automation = new Automation();
        for(int i=0;i<s.length();i++) {
            automation.get(s.charAt(i));
        }
        return (int) (automation.sign * automation.ans);
    }
    
    static class Automation{
        // sign表示符号位
        public int sign = 1;
        // ans表示数值的绝对值部分s
        public long ans = 0;
        private String state = "start";
        private Map<String,String[]> table = new HashMap<>();
        public Automation(){
            table.put("start", new String[]{"start","signed","number","end"});
            table.put("signed", new String[]{"end","end","number","end"});
            table.put("number", new String[]{"end","end","number","end"});
            table.put("end", new String[]{"end","end","end","end"});
        }

        /**
         * 状态转移过程
         * @param c
         */
        public void get(char c){
            state = table.get(state)[getCol(c)];
            // 在get当前c后查看所对应的状态，是否转移
            // 如果是number 则保存当前数值
            if("number".equals(state)){
                ans = ans * 10 + c - '0';
                ans = sign == 1? Math.min(ans,(long)Integer.MAX_VALUE) : Math.min(ans,-(long) Integer.MIN_VALUE);
            }else if("signed".equals(state)){
                sign = c == '+' ? 1 : -1;
            }
        }

        /**
         * 当前状态判断
         * i 表示第i列状态
         */
        private int getCol(char c) {
            if(c == ' '){
                return 0;
            }
            if(c == '+' || c == '-'){
                return 1;
            }
            if(Character.isDigit(c)){
                return 2;
            }
            return 3;
        }
    }
}

状态模式

TODO

推荐阅读