探索编译原理之有穷自动机DFA与NFA的介绍

1.前言

有穷自动机(Finite Automata, FA),是1948年,由两位神经物理学家MeCuloch和Pitts首先提出的,是对一类处理系统的建立数学模型。系统可以根据当前的状态以及目前的输入信息,产生后继的行为。有穷自动机由DFA(Deterministic finite automata)确定有穷自动机和NFA(Nondeterministic finite automata)非确定有穷自动机组成。

2.DFA的介绍

DFA由5元组构成,分别用 M = (S,Σ,δ,s0,F)表示。

S:有穷状态集

Σ :输入字母集合

δ :将S×Σ映射到S的转换函数,即代表状态S通过输入集合,确定并通过弧a到达后续的状态S

s0 :起始状态(有一个) s0 ∈ S

F:接收状态或者终止状态 F⊆ S

2.1 例子

DFA表示的是同一个输入,有且只有一个固定方向,线性的逻辑描述。比如有N个节点,这些节点就是S有穷的状态集合,从初始节点开始,通过读取输入的字符集,生成唯一一个到达后继节点的轨迹。比如:我现在需要设计一套题目,用于快速的筛选出逻辑能力强的人。但是,我不想让每个人都回答固定的N道题目,所以我想出了下面的设计思路。首先每个人都要回答一道初始题,这道题并没有准确的答案,而是一些反应推理能力强弱的伪答案。测试者,根据答案来回答下一道题。由于每个人的答案都不一样,所以,第二道题也不一样。有人能力强的,可能会直接跳转到终极题,有人能力弱的,可能顺序得回答逻辑上的第二题。

2.2 状态图及矩阵

根据上面测试题的设计,它的状态图如下所示:

0 1 2 3是状态(答题序号),而a和b则是(答题选项),而3是终结符,也可以认为是最后一道题。

对应的状态矩阵如下所示:

3.NFA的介绍

NFA和DFA同样由5元组构成, 分别用 M = (S,Σ,δ,s0,F)表示。

S:有穷状态集

Σ :输入字母集合

δ :将S×Σ映射到2^S的转换函数,即代表状态S通过输入集合,确定并通过弧a到达后续的状态S

s0 :起始状态(有一个) s0 ∈ S

F:接收状态或者终止状态(多个) F⊆ S

3.1 例子

NFA可以理解为多方向线性逻辑,就是输入字母会存在多条弧到达下一个后继状态。我用97拳皇格斗游戏中的出招算法,来当作举例。比如:草稚京的连招技能有:

1.下前、下前、轻拳

2.下前、下前、轻脚

3.2 状态图及矩阵

我们把动作细化到下、前、轻拳、轻脚。S状态抽象为指令,输入集合抽象为按键字母,则其NFA的状态图如下所示:

状态图有一个逻辑问题,那就是需要逻辑处理下前+下前的前置动作,因为图中,只要是行动指令+轻拳就能达到连招1,逻辑处理的部分,需要在编码的时候进行。

对应的状态矩阵如下图所示:

3.3 带有“ε-边”的 NFA

εNFA,当它到达后继状态时,无需通过输入字符表进行下一个后继状态的转换,而是直接可以转换到下一个后继状态。它的5元组和NFA类似, 分别用 M = (S,Σ,δ,s0,F)表示。

S:有穷状态集

Σ :输入字母集合

δ :将S×(Σ∪{ε})映射到2^S的转换函数,即代表状态S通过输入集合,确定并通过弧a到达后续的状态S,如果遇到 ε 边,则无需通过输入集合,直接达到后续的状态S。

s0 :起始状态(有一个) s0 ∈ S

F:接收状态或者终止状态(多个) F⊆ S

它的状态图如下所示:

当输入a时,它的状态有{0,1,2,3} (因为 ε 可以直接到达下一个状态

状态矩阵如下:

4.NFA转换为DFA

DFA是NFA的一个特殊子集,而NFA通过状态矩阵进行DFA的转换,下面,我们根据上面的出招NFA矩阵图进行状态图的转换。

NFA转DFA过程中,是从初始状态S开始遍历,所以此时的初始状态就是原先的S状态

5.从带有ε-边的NFA到DFA的转换

带ε边的转换方式和NFA转DFA相似,唯一不同的是,初始状态。它是从S开始遍历,由于ε的特性,一次它能遍历完所有的ε边。下面是上文中的εNFA转换成DFA的状态图:

6.遗留问题

NFA转换成DFA以后,我们看到更加的复杂,所以就有了DFA最小化的算法。DFA最小化的算法,我下次再更新。

7.参考

清华大学 《编译原理》张素琴 吕映芝

哈尔滨工业大学  陈鄞

如无特殊说明,文章均为本站原创,转载请注明出处。如发现有什么不对的地方,希望得到您的指点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注