确认有限状况自动机: 从游戏中学习并使用

1 前言

最近在码上上发现一个名为“机器人流水线(manufactoria)”的小游戏，复刻这个游戏对作者也对这个游戏的规矩和完成原理做了介绍。

今天咱们是来在游戏的玩法和通关思路上做文章的，因而假如不了解游戏规矩的话，可以阅览一下作者的介绍（最初的一小部分内容）。刚上手的时分或许对游戏的玩法和方针深感迷惑。这时分请务必坚持读一读介绍并实际操作一下。

当你在游戏中遇到困难，或许是成功通关了全部关卡，此刻再回头看一看这篇文章下面的内容，相信你能有所收获。

2 确认有限状况机

2.1 界说

什么是确认有限状况机，依据 Wiki 上的界说

确认有限状况自动机或确认有限自动机（英語：deterministic finite automaton, DFA）是一个能完成状况搬运的自动机。关于一个给定的属于该自动机的状况和一个属于该自动机字母表 $\Sigma$ 的字符，它都能依据事先给定的搬运函数搬运到下一个状况（这个状况可以是从前那个状况）。

他可以被方式化地界说为五元组：

确认有限状况自动机 $A{\displaystyle {\mathcal {A}}}$ 是由

一个非空有限的状况调集 $Q{\displaystyle Q}$

一个输入字母表（非空有限的字符调集） $\Sigma$

一个搬运函数 $:Q→Q{\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ （例如： $(q,)=p,(p,q∈Q,∈){\displaystyle \delta \left(q,\sigma \right)=p,\left(p,q\in Q,\sigma \in \Sigma \right)}$ ）

一个开端状况 $s∈Q{\displaystyle s\in Q}$

一个承受状况的调集 $F⊆Q{\displaystyle F\subseteq Q}$

所组成的5-元组。

因而一个DFA可以写成这样的方式： $A=(Q,,,s,F){\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)}$ 。

不过放一堆符号在这显得过于不流畅难懂了。下面我举个比如，并且用自然语言给咱们翻译一下:

状况调集便是状况机能表达的依据实际问题可以笼统出的全部状况。比如说咱们要评论一个人饿仍是饱的问题，就存在两个状况：饿，饱。
输入字母表可以了解为引起状况变化的所有原因。比如说，导致人饿或许饱的或许原因有：吃饭、喝水、运动等动作。
搬运函数代表状况调集和输入字母表的相关联系。比如说，“假如我饿了，我吃饭就饱了”，这一句话就说明晰 饿 --吃饭--> 饱 这一条搬运联系。
开端状况好了解，便是状况机初始处于哪个状况。比如说开端是饿的，或许是饱的。
承受状况代表了有限状况机的停止。便是说到达了什么状况后，状况机就完毕了，不行再运行。

2.2 使用

属于是计算理论的东西，常用于计算机科学的方式语言范畴和编译原理范畴。而这个思想也可以被用来辅助考虑和处理许多实际问题，比如说分析操作系统上程序的运行状况（此刻状况调集便是程序的仓库、寄存器等上下文信息），前端状况办理结构的规划，或许处理本文的游戏。

2.3 比如

下面举一个直观的比如来帮助咱们了解这些东西

状况调集: {饿，饱，死}
输入字母表: {吃饭，喝水，运动}
搬运函数:

吃饭	喝水	运动
饿	饱	饿	死
饱	死	饱	饿
死	–	–	–

开端状况：饿
完毕状况：{死}

graph LR
饿((饿))
饱((饱))
死((死))
饿 --吃饭--> 饱
饿 --喝水--> 饿
饿 --运动--> 死
饱 --吃饭--> 死
饱 --喝水--> 饱
饱 --运动--> 饿

2.4 代码

假如你觉得理论知识仍是不够明晰，拿手经过代码了解的话，可以看看下面依据 Java 状况机模式的 Demo

// State.java
/**
 * 笼统状况接
 * 每一个办法对应一个输入字母表中的元素
 * 每一个办法回来搬运到的下一个状况
 */
public interface State {
    State eat();
    State drink();
    State exercise();
}

// StateHungry.java
/**
 * 饥饿状况
 */
public class StateHungry implements State {
    @Override
    public State eat() {
        System.out.println("饿 --吃饭--> 饱");
        return Context.STATE_FULL;
    }
    @Override
    public State drink() {
        System.out.println("饿 --喝水--> 饿");
        return Context.STATE_HUNGRY;
    }
    @Override
    public State exercise() {
        System.out.println("饿 --运动--> 死");
        return Context.STATE_DEAD;
    }
}

// StateFull.java
/**
 * 饱腹状况
 */
public class StateFull implements State {
    @Override
    public State eat() {
        System.out.println("饱 --吃饭--> 死");
        return Context.STATE_DEAD;
    }
    @Override
    public State drink() {
        System.out.println("饱 --喝水--> 饱");
        return Context.STATE_FULL;
    }
    @Override
    public State exercise() {
        System.out.println("饱 --运动--> 饿");
        return Context.STATE_HUNGRY;
    }
}

// StateDead.java
/**
 * 死亡状况
 */
public class StateDead implements State {
    @Override
    public State eat() {
        System.err.println("承受状况，不行搬运");
        return Context.STATE_DEAD;
    }
    @Override
    public State drink() {
        System.err.println("承受状况，不行搬运");
        return Context.STATE_DEAD;
    }
    @Override
    public State exercise() {
        System.err.println("承受状况，不行搬运");
        return Context.STATE_DEAD;
    }
}

// Context.java
public class Context {
		// 状况单例
    public static final State STATE_HUNGRY = new StateHungry();
    public static final State STATE_FULL = new StateHungry();
    public static final State STATE_DEAD = new StateHungry();
    private State currentState;
    public Context() {
        this(STATE_HUNGRY);
    }
    public Context(State initState) {
        currentState = initState;
    }
    void eat() {
        currentState.eat();
    }
    void drink() {
        currentState.drink();
    }
    void exercise() {
        currentState.exercise();
    }
}

2.4 工作方式

确认有限状况自动机从起始状况开端，一个字符接一个字符地读入一个字符串 $w∈∗{\displaystyle w\in \Sigma ^{*}}$ （这儿的 $∗{\displaystyle {}^{*}}$ 指示Kleene星号算子。），并依据给定的搬运函数一步一步地搬运至下一个状况。在读完该字符串后，假如该自动机停在一个属于F的承受状况，那么它就承受该字符串，反之则回绝该字符串。

简略地来说，关于确认有限状况自动机可以用来检验一个字符序列是不是契合规矩的。

检测的进程为：

从初始状况开端，按顺序读取字符序列中的每一个字符
不断依据读入的字符进行状况搬运
假如最终可以处于“承受状况”，那么这个字符序列便是合法的
假如读到一半发现搬运不了，或许读完了不处于“承受状况”，那么这个字符序列便是不合法的。

这儿其实对流程做了简化。严格依照界说，有必要在读完所有字符后处于承受状况

3 状况机与游戏

该游戏的第1关至第7关处理的是同一类问题，即验证给定的输入序列是否满足特定的条件。

结合 2.4 工作方式，发现这两者之间确实是存在联系的。

于是咱们将处理这个游戏的问题转化为以下两个步骤：

依据每个关卡的要求，树立状况机模型
使用游戏中的元件，将状况机模型表明出来

3.1 树立状况机模型

不难了解，以下是针对这个游戏可以树立的通用状况机模型

状况调集: 依据标题笼统出「合法」的状况
- 输入字母表: {开端完毕符 #，红球，蓝球}
搬运函数: 依据标题笼统
开端状况: {开端}
承受状况: {成功}

其间，咱们为每一个检测序列的最初和完毕添加符号 #，便于表明出“序列开端”和“序列完毕”两种语义。例如，关于序列 {红，红，蓝}，咱们在状况机分析进程中认为他是 { # ，红，红，蓝， #}

而状况调集需要依据标题进行笼统，这便是一个思想进程了（毕竟是个思想游戏）。不过这一思想进程是人类可以从多个比如从学习出潜在经验的。以下给出几个比如：

承受2个及以上蓝球的序列：{已承受0个蓝球，已承受1个蓝球，已承受2个蓝球}
行列有必要以2个蓝球完毕：{已接连0个蓝球，已接连1个蓝球，已接连2个蓝球}
行列中不能呈现红球：{未承受过红球} 由于一旦呈现红球便是非法状况了

最终是搬运函数的笼统，也是思想进程。针对上一步现已笼统出的状况调集，考虑这样一个问题 「状况A承受输入字母表c中的字母后，会搬运到哪个状况」，例如：

承受2个及以上蓝球的序列：「已承受0个蓝球」假如输入一个「蓝球」就会搬运到「已承受1个蓝球」，那么就有转化联系
```
graph LR
S1((已承受0个蓝球)) --蓝球--> S2((已承受1个蓝球))
```
行列中不能呈现红球：「未承受过红球」假如输入一个「蓝球」就会搬运到「未承受过红球」，那么就有转化联系（假如输入红球就失利了，由于依据前面的界说，不能读到一半就搬运不下去）
```
graph LR
S1((行列里未呈现红球)) --蓝球--> S1((行列里未呈现红球))
```

3.2 表明状况机模型

从树立好的状况机模型到游戏组件的表明是比较呆板的进程。

状况机中的每个状况是必然会依据下一个输入搬运的，这一行为和游戏中的「比较器」完全符合
状况搬运中的自环，可以用一个指向「比较器」本身的箭头表明

状况搬运中不存在的搬运联系，「比较器」对应的移动方位留白（这样就肯定到达不了终点了）

考虑每个状况关于输入 # 的搬运联系，他代表“序列完毕”，也就意味着这个状况对应的「比较器」将往弧形方向移动

4 关卡攻略

以下解法均为个人通关思路，仅供参考

4.1 第1关

第1关没有什么难点，纯粹是让新手了解游戏流程和操作模式的

graph LR
Start((开端)) --#--> E1((E1))
E1 --#--> Success((成功))

4.2 第2关

第2关用于了解比较器的使用办法。

在完成上，依据前文所述，咱们可以将一个比较器视为一个状况，依据下一个状况的不同指向不同的分支。

graph LR
Start((开端))
S1((S1))
Success((成功))
Start --#--> S1
S1 --蓝--> Success

4.3 第3关

在状况机的结构上，标题是要求序列中有3个及以上蓝球。从状况搬运的视点考虑，便是接收到红球时就坚持状况不变；接收到蓝球时搬运至下一个状况；接收到完毕符号 # 时，有必要处于现已接收了3个蓝球的状况，不然就失利。

在完成上，主要是使用比较器表达自环的状况，使用一个指向比较器自己的箭头元件就能完成。

S1: 已承受0个蓝球
S2: 已承受1个蓝球
S3: 已承受2个蓝球

graph LR
Start((开端))
S1((S1))
S2((S2))
S3((S3))
Suc((成功))
Start --#--> S1
S1 --红--> S1
S1 --蓝--> S2
S2 --红--> S2
S2 --蓝--> S3
S3 --红--> S3
S3 --蓝--> Suc

4.4 第4关

在状况机的结构上，标题是要求序列不能有红球。那么咱们就先走完整个序列，一旦遇到红球就失利，遇到蓝球就坚持状况不变。只要不失利（也便是没有遇到红球），那么遇到完毕符 # 时就说明成功。

在完成上，也是使用比较器结构自环状况。

S1: 未承受过红球

graph LR
Start((开端))
S1((S1))
Suc((成功))
Start --#--> S1
S1 --蓝--> S1
S1 --#--> Suc

4.5 第5关

这一关相比前面的关卡复杂了一些。

在状况机的结构上，标题要求不能呈现不同色彩的球。换句话说，一旦第一个球是蓝色，那么后面的球也有必要都是蓝色；一旦第一个球是赤色，那么后面的球也有必要都是赤色。依据这个思路的转化，结合上一关的通关思路，就能处理这个问题了。

S1: 未承受任何球
S2: 已承受蓝球
S3: 已承受红球

graph LR
Start((开端))
S1((S1))
S2((S2))
S3((S3))
Suc((成功))
Start --#--> S1
S1 --蓝--> S2
S1 --红--> S3
S2 --蓝--> S2
S3 --红--> S3
S1 --#--> Suc
S2 --#--> Suc
S3 --#--> Suc

4.6 第6关

第6关是要检验以两个蓝色球完毕的序列。可以结合第3关的思路，碰到蓝球的时分就搬运到下一个状况，碰到红球时就回来最开端的状况。碰到完毕符 # 时有必要处于现已接连碰到2个蓝球的状况才干成功。

S1: 已接连承受0个蓝球
S2: 已接连承受1个蓝球
S3: 已接连承受2个蓝球

graph LR
Start((开端))
S1((S1))
S2((S2))
S3((S3))
Suc((成功))
Start --#--> S1
S1 --红--> S1
S1 --蓝--> S2
S2 --红--> S1
S2 --蓝--> S3
S3 --红--> S1
S3 --蓝--> S3
S3 --#--> Suc

4.7 第7关

这一关是要验证序列的最初和完毕球色彩相同。从状况的视点考虑，首先最初的球的色彩肯定是要做一个分支的。咱们以最初为红球的路线为例（最初为蓝球的状况是对称的），当咱们遇到完毕符 # 的时分，假如前一个球是红球，那么就成功；假如前一个球是蓝球，那么就失利。因而，在序列的解析进程中，咱们可以不断地在“行将成功”和“行将失利”两个状况间搬运，即遇到红球是搬运到“行将成功”状况，遇到蓝球是搬运到“行将失利状况”。

S1: 未承受任何球
S2: 行列最初为红球
S3: 行列最初为红球，最近接收到的是蓝球
S4: 行列最初为蓝球
S5: 行列最初为蓝球，最近接收到的是红球

graph LR
Start((开端))
S1((S1))
S2((S2))
S3((S3))
S4((S4))
S5((S5))
Suc((成功))
Start --#--> S1
S1 --红--> S2
S1 --蓝--> S4
S2 --红--> S2
S2 --蓝--> S3
S3 --红--> S2
S3 --蓝--> S3
S4 --红--> S5
S4 --蓝--> S4
S5 --蓝--> S4
S5 --红--> S5
S1 --#--> Suc
S2 --#--> Suc
S4 --#---> Suc

5 课后作业

除了第1关至第7关外，还有第11关和第13关也可以用有限状况机的思想处理。其间第11关和上述某个关卡的处理方案是类似的，而第13关或许需要一点点的技巧对标题做一些转化。相信读者在看完这篇文章之后，可以自己经过自己的考虑和对状况机的运用处理这两关。

这两关的解题思路将在下一期揭晓（假如还有下一期的话）。

确定有限状态自动机: 从游戏中学习并应用

确认有限状况自动机: 从游戏中学习并使用

1 前言

2 确认有限状况机

2.1 界说

2.2 使用

2.3 比如

2.4 代码

2.4 工作方式

3 状况机与游戏

3.1 树立状况机模型

3.2 表明状况机模型

4 关卡攻略

4.1 第1关

4.2 第2关

4.3 第3关

4.4 第4关

4.5 第5关

4.6 第6关

4.7 第7关

5 课后作业

作者信息

确定有限状态自动机: 从游戏中学习并应用

确认有限状况自动机: 从游戏中学习并使用

1 前言

2 确认有限状况机

2.1 界说

2.2 使用

2.3 比如

2.4 代码

2.4 工作方式

3 状况机与游戏

3.1 树立状况机模型

3.2 表明状况机模型

4 关卡攻略

4.1 第1关

4.2 第2关

4.3 第3关

4.4 第4关

4.5 第5关

4.6 第6关

4.7 第7关

5 课后作业

相关文章

如何让程序更健壮「GitHub 热点速览」

Rust UI 框架：用 Rust 和 Slint 制作一个简易计算器(Live coding )

App 黑白化技术实践下篇

URL长链接转短链接：为什么成为现代社会中必不可少的技术？

作者信息