type
status
date
slug
summary
tags
category
icon
password
自动机
有限自动机（FA）：有限自动机的有限表示的状态的有限，其后继可能是自身，也可能是单一的其他状态，也可能是多个其他状态
确定有限自动机（DFA）：首先确定有限自动机是一个有限自动机，所以状态是有限的。其次他是确定的，也就是每次状态转换的时候当前状态的后继状态是唯一的。
西格玛可以理解为是每一次状态转移条件的集合（比如输入一个a，确定自动机就会从一个状态转移到另一个状态，这个时候a就属于西格玛）
f是从S西格玛到S的一个映射，就是说f的定义是，S中的某个状态识别了西格玛中的某个符号（S\西格玛）之后，经过f的运算会对应S中的一个状态（S），而f是单值映射就说明了每次识别一个符号只能转移到S中的单一状态，也就是确定有限自动机的确定的含义
注意这里终态集也是算在有限状态集中的，也就是终态集是有限状态集的一个子集（终态可能不唯一），但是初态是算在有限状态集中的（初态是唯一的）
状态转换可以用这个矩阵表示
其中左下角代表有限状态集，右上角代表符号表，右下角代表f运算出的状态转移结果
非确定有限自动机（NFA）：非确定有限自动机的状态也是有限的（因为是有限自动机），但是每次状态转换的时候当前状态的后继状态就不是唯一的了
这里可以发现非确定有限自动机相对于确定有限自动机的区别主要有以下两点：
- 初态有多个，构成初态集Q（初态集是有限状态集合的子集）
- f是一个从S*西格玛到S的多值映射（对应着非确定）
这些区别体现为下面的三个特征
前两条就是上面说的区别，最后一条很重要（字就是字母表中的值，能接收空串说明非确定有限自动机从一个状态转移到另一个状态可以不需要识别字，这个时候假如一个出边有空边，那么到这个状态的上一个状态的下一个状态就不是唯一的，也就对应了非确定有限自动机的非确定），所以如果一个有限自动机存在空边，那么他一定是一个非确定有限自动机（所以非确定有限自动机转换为确定有限自动机的时候需要进行空闭包运算）
字母表上的乘积运算（就是笛卡尔积结果的每一个元素都拼在一起）
正闭包的运算（后面求空闭包的时候就会用到）
克林闭包运算（也就是空闭包运算，在正闭包的基础上多加了一个空串）
自动机从起点到终点的一条通路对应一个自动机能识别的串，这些串构成的集合就是自动机能识别的语言，记为L（M），其中M是自动机的符号。如果两个识别的语言相同，那么两个自动机就是等价的
确定自动机只要运行一次但是非确定自动机要运行若干次主要是因为确定自动机对一个输入串每一个节点上的状态转移都是确定的，但是非确定自动机是不确定的，这个时候非确定自动机就需要回溯（这里也就是自动机的重启，因为没有记录非确定自动机之前的状态）
一个非确定自动机的画法，或的话就两条边并联，与的话就两条边串联，出现若干（星号）的时候就在两个结点之间再加一个节点，在节点上画回边（如果是加号的话就独立出来一次保证成立，剩下的就跟星号是一样的了）
非确定自动机的自动化主要就是看某一个状态识别了一个字之后能转换到哪些状态，将这些状态合在一起成为一个状态就好了（所以要做当前识别字符的闭包运算和空闭包运算）
这句话也就是这个意思，这里的K子集就是某一个状态的所有后继状态，然后乘号后面是西格玛∪空是因为非确定自动机是能识别空串的
这里第一步应该是克林闭包的，但是下一步就能将克林闭包化为西格玛∪空，这是因为克林闭包本质上就是一串字和空串的组合，也就是非确定自动机能识别的串（但是这个时候肯定是有很多串不是自动机能识别的语言，也就是有的串是没办法走到结束状态的，但是克林闭包是一种枚举的思想，全部列出来总不会错吧），这个时候自动机其实是进行了多次状态转移的，所以第一个式子的含义就是自动机经过多次状态转移之后到达了哪些状态，这个时候如果要进行确定化的话，这些最终的状态就是要是确定的（这样才能将这些状态合在一起变成一个状态）。识别一个串结果状态确定，就等价于识别一个字符下一个状态固定（也就是只需要满足克林闭包的前两项就好了），这样就推出来了第二个式子
空闭包运算，就是一直识别一个空
所以非确定自动机的自动化本质上就是从一个状态开始，识别一个字，然后一直从这个状态开始，向后识别这个字和空（一直做空闭包运算还有该字的闭包运算）
这里的Iai应该就是闭包运算的意思，第四条规则就是将一个新状态（未在第一列出现的状态）置为下一行的开始状态，也就是将自动机串起来
这个表里面的I也是闭包运算的意思
注意非确定自动机确定化的时候前面的状态不一定在后面的状态内部，还是要看经过闭包运算之后能否到达
所以这个时候计算识别一个字后的状态应该这样来处理：
- 先识别一个当前字（当前状态内部每个状态逐个判断）
- 然后进行空闭包运算（对第一步产生的新状态集合进行空闭包运算）
一定是先识别一个当前字是因为产生当前状态的时候的那一次计算，已经进行了一次空闭包运算，所以这个时候当前状态内部的某个状态就已经是待判断状态识别一个空串后的结果了，所以空串没必要再进行识别（因为上一次已经识别了）
画出来线性规划闭包运算的图了之后就像上图一样直接进行状态的替换就好了（注意所有包含原状态的结束状态的新状态都是结束状态，包含原状态的开始状态的新状态就是初始状态）
并不是说结束状态之后不能再连东西了，而是说当输入串结束的时候，如果当前状态是结束状态就说明这个串被自动机接受了，如果不是结束状态就说明自动机没办法识别这个串
也就是说，自动机没有接受有两种情况
- 串识别结束，但是最后的状态不是结束状态
- 串没有识别结束，但是当前状态没办法识别当前字符了（也就是没办法进行状态转移了），这个时候也需要停机
- 作者:Noah
- 链接:https://imnoah.top/article/Compiler/Chapter0
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。