某个有限自动机，如果每次状态转换的后继状态都是惟一的，则称它是确定有限自动机（DFA）；如果转换后的后继状态并不都是惟一的，则称它是不确定有限自动机（NFA）。
有限自动机的开始工作状态称为初始状态，结束工作的状态称为终止工作状态或接收状态。如果把上一小节中的状态转换图的各个结点看成是某一个状态，初始结点为初始状态，终止结点为终止状态，并且每一条边表示一个转换关系，这样一个有限自动机的工作状态就可以采用状态转换图来描述了，从而可以把前面的图看成是一个有限自动机。
有限自动机处在初始状态0，当读入符号a后，自动机便从状态0转换到后继状态1中，再读入一个符号b后，自动机便从状态1转换到后继状态2。当自动机读入一个符号串，自动机则从初始状态开始，经过一系列状态转换，最终若能够到达终止状态，则称这一符号串被该自动机所接收或识别，否则不能被该自动机所接收。
一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：
- K是一个有穷非空集，集合中的每个元素称为一个状态；
- ∑是一个有穷字母表，∑中的每个元素称为一个输入符号；
- F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；
- S∈K，是惟一的初态；
- ZK，是一个终态集。
由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。
对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。
一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：
- k是一个有穷非空集，集合中的每个元素称为一个状态；
- ∑是一个有穷字母表，∑中的每个元素称为一个输入符号；
- F是一个从K×∑→K的子集的转换函数；
- SK，是一个非空的初态集；
- ZK，是一个终态集。
由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：
（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；
（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。
因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。
对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。
由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。
设M1和M2是同一个字母集∑上的有限自动机，若L（M1）＝L（M2），则称有限自动机M1和M2等价。
由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFA M1总存在一个DFA M2，使得L（M1）＝L（M2）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。
NFA确定化为DFA
同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。
下面介绍一种NFA的确定化算法，这种算法称为子集法：
- 若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为：
S＝[S1，S2，…，Sn]，
其中方括号用来表示若干个状态构成的某一状态。
- 设DFA的状态集K中有一状态为[Si，Si+1，…，Sj]，若对某符号a∈∑，在NFA中有F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }
则令F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }为DFA的一个转换函数。若[ Si’，Si+1’，…，Sk‘ ]不在K中，则将其作为新的状态加入到K中。
- 重复第2步，直到K中不再有新的状态加入为止。
- 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。
- DFA中凡是含有NFA终态的状态都是DFA的终态。
对于上述NFA确定化算法——子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。
假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为：
- 若Q∈I，则Q∈ε-closure（I）；
- 若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈ε-closure（I）。
状态集ε-closure（I）称为状态I的ε闭包。
假设NFA M＝（K，∑，F，S，Z），若I∈K，a∈∑，则定义Ia＝ε-closure（J），其中J是所有从ε-closure（I）出发，经过一条a弧而到达的状态集。
NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。
C++代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
// // main.cpp // compiling3 // // Created by 徐奕 on 2018/11/6. // Copyright © 2018 Reacubeth. All rights reserved. // #include <iostream> #include <vector> #include <set> #include <cstdio> #include <algorithm> using namespace std; struct Part{ string src; string edge; string dst; }; void input(vector<Part> &NFA, int num){ for(int i=0;i<num;i++){ Part temp; //scanf("%s,%s,%s",&temp.src,&temp.edge,&temp.dst); cin>>temp.src>>temp.edge>>temp.dst; NFA.push_back(temp); } } void outputNFA(vector<Part> NFA){ for(int i=0;i<NFA.size();i++){ cout<<NFA[i].src<<" "<<NFA[i].edge<<" "<<NFA[i].dst<<endl; } } bool check(string str, char x){ for(int i=0;i<str.length();i++){ if(str[i]==x) return true; } return false; } string closure(string setp, vector<Part> NFA){ for(int i=0;i<setp.length();i++){ for(int j=0;j<NFA.size();j++){ if(setp[i]==NFA[j].src[0]&&NFA[j].edge[0]=='&'){ if(!check(setp,NFA[j].dst[0])){ setp+=NFA[j].dst[0]; } } } } return setp; } string move(string t, char a, vector<Part> NFA){ string temp=""; for(int i=0;i<t.length();i++){ for(int j=0;j<NFA.size();j++){ if(t[i]==NFA[j].src[0]&&NFA[j].edge[0]==a){ if(!check(temp,NFA[j].dst[0])){ temp+=NFA[j].dst[0]; } } } } return temp; } bool checkINrawDFA(vector<string> rawDFA, string u){ for(int i=0;i<rawDFA.size();i++){ if(rawDFA[i]==u) return true; } return false; } int checkFlag(vector<bool> t){ for(int i=0;i<t.size();i++){ if(t[i]==false)return i; } return -1; } int main(int argc, const char * argv[]) { vector<Part> NFA; int num; cout<<"input: "; cin>>num; getchar(); input(NFA,num); //outputNFA(NFA); char sigma[2]={'a','b'};//字母表 string start = closure("0", NFA);//k起始符的闭包 sort(start.begin(), start.end()); vector<string> rawDFA;//存入子集 rawDFA.push_back(start); vector<bool> rawDFAflag;//存入子集是否完成的标志 rawDFAflag.push_back(false); cout<<endl; while(checkFlag(rawDFAflag)!=-1){ int m = checkFlag(rawDFAflag); rawDFAflag[m]=true; for(int i=0;i<2;i++){ string u = closure(move(rawDFA[m],sigma[i],NFA), NFA); sort(u.begin(), u.end()); if(!checkINrawDFA(rawDFA, u)){ rawDFA.push_back(u); rawDFAflag.push_back(false); } } } cout<<endl; for(int i=0;i<rawDFA.size();i++){ cout<<rawDFA[i]<<" "<<closure(move(rawDFA[i],'a',NFA),NFA)<<" "<<closure(move(rawDFA[i],'b',NFA),NFA)<<endl; } return 0; } /* 0 & 1 1 a 2 1 a 4 1 b 3 2 a 5 4 b 5 3 a 5 */ /* 0 & 1 1 a 1 1 b 1 1 & 2 2 a 3 2 b 4 3 a 5 4 b 5 5 & 6 6 a 6 6 b 6 6 & 7 */ |
Python代码（利用graphviz画图）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 |
from graphviz import Digraph class Part: def __init__(self, src, edge, dst): self.src = src self.edge = edge self.dst = dst def check(str, x): for i in range(len(str)): if str[i]==x: return True return False def closure(setp, NFA): t = len(setp) i = 0 while i < t: for j in range(len(NFA)): if setp[i] == NFA[j].src[0] and NFA[j].edge[0]=='&': if not check(setp, NFA[j].dst[0]): setp += NFA[j].dst[0] t += 1 i += 1 return setp def move(t, a, NFA): temp = "" for i in range(len(t)): for j in range(len(NFA)): if t[i] == NFA[j].src[0] and NFA[j].edge[0]==a: if not check(temp, NFA[j].dst[0]): temp += NFA[j].dst[0] return temp def checkINrawDFA(rawDFA, u): for i in range(len(rawDFA)): if rawDFA[i] == u: return True return False def checkFlag(t): for i in range(len(t)): if t[i]==False: return i return -1 def checkINdex(rawDFA, u): for i in range(len(rawDFA)): if rawDFA[i] == u: return i return -1 NFA = [] NFA2 = [] NFADic = {} dot = Digraph(comment='The Test Table') num = int(input('input:')) for i in range(num): x = input() y = input() z = input() temp = [] temp.append(int(x)) temp.append(int(z)) NFA2.append(temp) NFADic[tuple(temp)] = y temp = Part(x, y, z) NFA.append(temp) dot.node(x, x) dot.edge(x, z, y) # dot.render('NFA.gv', view=True) for i in range(len(NFA)): print(NFA[i].src, NFA[i].edge, NFA[i].dst) sigma = ['a', 'b'] start = closure("0", NFA) start = "".join(sorted(start)) rawDFA = [] rawDFA.append(start) rawDFAflag = [] rawDFAflag.append(False) while checkFlag(rawDFAflag) != -1: m = checkFlag(rawDFAflag) rawDFAflag[m] = True for i in range(len(sigma)): u = closure(move(rawDFA[m], sigma[i], NFA), NFA) u = "".join(sorted(u)) if not checkINrawDFA(rawDFA, u): rawDFA.append(u) rawDFAflag.append(False) DFA = [] DFA2 = [] DFADic = {} for i in range(len(rawDFA)): print(rawDFA[i], closure(move(rawDFA[i], 'a', NFA), NFA), closure(move(rawDFA[i],'b',NFA),NFA)) DFA.append(rawDFA[i]) dot2 = Digraph(comment='The Test Table') for i in range(len(DFA)): temp = [] temp.append(i) temp.append(checkINdex(rawDFA, "".join(sorted(closure(move(rawDFA[i], 'a', NFA), NFA))))) DFA2.append(temp) DFADic[tuple(temp)] = 'a' temp = [] temp.append(i) temp.append(checkINdex(rawDFA, "".join(sorted(closure(move(rawDFA[i], 'b', NFA), NFA))))) DFA2.append(temp) DFADic[tuple(temp)] = 'b' dot2.node(str(i), str(i)) dot2.edge(str(i), str(checkINdex(rawDFA, "".join(sorted(closure(move(rawDFA[i], 'a', NFA), NFA))))),'a') dot2.edge(str(i), str(checkINdex(rawDFA, "".join(sorted(closure(move(rawDFA[i], 'b', NFA), NFA))))),'b') dot2.render('DFA.gv', view=True) ''' 0 & 1 1 a 1 1 b 1 1 & 2 2 a 3 2 b 4 3 a 5 4 b 5 5 & 6 6 a 6 6 b 6 6 & 7 ''' ''' 0 a 1 0 b 2 1 b 2 2 a 1 1 a 3 2 b 3 3 a 3 3 b 3 ''' |
验证
测试数据1：
0 & 1
1 a 1
1 b 1
1 & 2
2 a 3
2 b 4
3 a 5
4 b 5
5 & 6
6 a 6
6 b 6
6 & 7
其NFA如下图所示（使用graphviz生成），0是初态，7是终态。
结果1：
子集生成过程的矩阵表示，第一列是子集，第二列是move(t,a)操作，第三列是move(t,b)操作。
转换后的DFA如下图所示（使用graphviz生成，其中3，4，5，6是终态）
测试数据2：
0 a 1
0 b 2
1 b 2
2 a 1
1 a 3
2 b 3
3 a 3
3 b 3
NFA2：
生成的DFA（和NFA相同上图）
难点
基本算法是子集法，核心函数是move和closure函数。
遇到的问题:
- 如何构造子集的数据结构才能方便而快速地从NFA转化为DFA。解决的方案使用字符串作为子集，比如“abc”则是代表状态a,b和c的集合。
- 生成的DFA的编号问题，需要根据Move和closure的结果动态编号
- 图形化界面显示，一开始使用的是python中的networkx，最后发现networkx不能画自环路，于是最后换成了graphviz来进行图形界面的展示。
