0%

DFA最小化算法

前段时间帮同学写作业:dfa的最小化算法。

部分写法是为了照顾作业的基本要求,写的时候也比较随意。

原理简述

  1. 将原DFA中的所有结点根据是否是终结状态结点分为两个集合(endset与notendset),并把这两个集合放入队列q中。
  2. 对队列q的中每一个集合做如下操作,直到队列为空:
    • 取出队列中的第一个元素集合命名为tmp,取出它的第一个值命名为fir
    • 对tmp中的每个元素(除了fir)在所有可能的输入下,确定其转移结点与fir在相同输入下得到的转移节点是否等价(是否在同一个集合内),若不等价则做不等价标记。
    • 对tmp中的每个元素(除了fir),若无不等价标志则该元素与fir是一个等价结点,否则与fir是一个不等价结点。
      我们把tmp中与fir不等价的结点保存到一个集合(setToQueue)中并放入队列q。
      与fir等价的结点结点保存到一个集合(setToRes)中,并放入全局变量resset。
  3. resset中的若干个集合就是原DFA和最小化后DFA的对应关系,将其转化为新的结点。
  4. 遍历原DFA中的每一条边,根据resset中的对应关系,将其转化为最小化后DFA的边。

考虑到以下过程的实现难度:在对一个集合内的元素通过相同输入分成若干个集合。 所以在算法原理上做了一定修改。修改为每次只分成两个集合:和集合第一个元素等价的,不等价的。这样会多进行几次集合的划分但实际上的效率并没有下降多少,反而在编码难度上大大降低。

实现中:“使用队列不断的对队列中第一个集合进行划分,直到队列为空”的想法在一定程度上借鉴了BFS(广度优先搜索)的思想,区间划分的结果视为一颗树,即是树的层序遍历。

在实现中还可以使用优先队列,将非终态结点和集合中首元素下表小的放到前面。这样形成的新的DFA在整体上会更贴近原DFA,如使用样例中若是结果顺序是{ 0 }{ 1 }{ 2 }{ 3 4 5 6 },则在阅读顺序上更友好,但不影响算法本质,故没有实现。

输入输出描述

这部分可对照末尾的样例阅读

输入描述

第一部分为整数n,m。n是原DFA的状态结点数,m是从状态节点转移的边数。
第二部分是n个0/1的数字,第i个数字表示第i个状态结点是否是结束结点(1是结束结点,0不是)。
第三部分是m行,每行2个整数(u和v)和一个字符(ch),表示u号状态节点经过输入ch转移到v号状态节点。所有的状态结点标号都从0开始。

输出描述

第一部分为如S1 = { 3 4 5 6 } end的多个式子,表示最小化后的DFA中的1号结点是原DFA中3,4,5,6号结点的等价合并,并且它是一个终结状态结点(若不是终结结点则无end)。
第二部分是如S0 S2 a形式的多个式子,表示S0状态节点经过输入a到达S2状态结点。

代码简述

数据结构描述

Edge:
使用了一个pair来模拟,即DFA的某个结点在输入char下转移到int号结点。

Node:

  • listl 来保存该Node的相关的边
  • flagEnd 用来标记这是否是一个终结结点
  • flagTmp 用于方便算法流程的操作
  • idx 表示该结点的下标(并没有什么用

Set:
使用了vector来模拟集合的概念

整体过程描述

主函数中依次调用init,readDfa,minimize,build函数,其作用如下:

函数 功能

init| 初始化部分全局变量
readDfa| 读输入数据,构建原DFA
minimize| 最小化的过程:将等价状态节点转换成一个集合
build| 对最小化得到的集合进行边的构建,形成新的DFA

  1. fa数组在minimize的过程中的作用是确定两个结点是否等价,即fa[3]=2,fa[5]=2代表3号结点和5号结点是等价的。fa的值为结点所在集合中第一个结点的标号。
  2. 把所有的输入字符保存在了全局变量setCh中,要求对tmp中的每个元素和fir在相同输入下的结果判断是否等价,实现方法是对每个结点上打一个标记(Node中的flagTmp),先初始化为true,若得到了不同的结果则标记为false。然后对tmp中每个结点进行检查,true代表等价,false表示不等价。
  3. 在更新setToQueue和setToRes时还要记得在更新fa的值,即重新确定相关结点所属的集合。
  4. 因为我们保存边的方式是链表,所以在build的过程中需要判断加入新DFA中的边是否已经存在,若不存在才加入,以免数据冗余与不必要的错误。(使用Node中的findInlist函数完成)。
  5. 对于新DFA中的结点是否是终结结点,只需要判断其代表的任意一个原DFA结点是否是终结结点即可。
  6. fa数组在build的过程中代表的是原DFA在新DFA中的所属关系,如fa[2]=3表示原来的2号结点与最小化后的DFA的3号结点等价。

源代码

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
#include 
using namespace std;
const int maxn = 1e4 + 10;
typedef pair<int, char> edge;
typedef vector<int> Set;

struct Node
{
list l;
bool flagEnd, flagTmp;
int idx;
Node(int i, bool f) : flagEnd(f), idx(i)
{
flagTmp = false;
}
bool findInList(int u, char c)
{
for (auto i = l.begin(); i != l.end(); ++i)
{
if (edge(u, c) == *i)
return true;
}
return false;
}
int find(char c)
{
for (auto i : l)
{
if (i.second == c)
{
return i.first;
}
}
return -1;
}
};

int n, m;
vector nodes;
vector resset;
Set endset, notendset;
vector<char> setCh;
int fa[maxn];
void init()
{
nodes.clear();
memset(fa, -1, sizeof fa);
resset.clear();
setCh.clear();
}
void readDfa()
{
cin >> n >> m;
bool flag;
int v, u;
char ch;
for (int i = 0; i < n; ++i)
{
cin >> flag;
nodes.push_back(Node(i, flag));
fa[i] = i;
if (flag == 1)
{
endset.push_back(i);
}
else
{
notendset.push_back(i);
}
}
for (int i = 0; i < m; ++i)
{
cin >> u >> v >> ch;
setCh.push_back(ch);
nodes[u].l.push_back(edge(v, ch));
}
}
void minimize()
{
queue q;
q.push(notendset);
q.push(endset);

if (!endset.empty())
{
for (int i = 0; i < endset.size(); ++i)
fa[endset[i]] = endset[0];
}
if (!notendset.empty())
{
for (int i = 0; i < notendset.size(); ++i)
fa[notendset[i]] = notendset[0];
}
while (!q.empty())
{
Set tmp = q.front();
q.pop();
if (tmp.empty())
continue;
Set setToQueue;
Set setToRes;
int fir = tmp[0];
setToRes.push_back(fir);

for (int i = 0; i < tmp.size(); ++i)
{
nodes[tmp[i]].flagTmp = true;
}
for (int i = 0; i < setCh.size(); ++i)
{
int left = nodes[fir].find(setCh[i]);
for (int j = 1; j < tmp.size(); ++j)
{
int now = tmp[j];
if (nodes[now].flagTmp == false)
continue;
int right = nodes[now].find(setCh[i]);
if (fa[left] != fa[right])
{
nodes[now].flagTmp = false;
}
}
}
int u = -1;
for (int i = 1; i < tmp.size(); ++i)
{
int now = tmp[i];
if (nodes[now].flagTmp == false)
{
setToQueue.push_back(now);
if (u == -1)
u = now;
fa[now] = u;
}
else
{
setToRes.push_back(now);
}
}
q.push(setToQueue);
resset.push_back(setToRes);
}
}
vector newDfa;
int main()
{
init();
readDfa();
minimize();
int Sid = 0;
for (int i = 0; i < resset.size(); ++i)
{
Set tmp = resset[i];
bool flag = false;
cout << "S" << Sid << " = { ";
for (int j = 0; j < tmp.size(); ++j)
{
cout << tmp[j] << " ";
fa[tmp[j]] = Sid;
}
cout << "} ";
if (nodes[tmp[0]].flagEnd == true)
{
cout << "end";
flag = true;
}
cout << endl;
newDfa.push_back(Node(Sid++, flag));
}
for (int i = 0; i < n; ++i)
{
int fu = fa[i];
list tmp = nodes[i].l;
for (auto j = tmp.begin(); j != tmp.end(); ++j)
{
int fv = fa[(*j).first];
if (!newDfa[fu].findInList(fv, (*j).second))
{
newDfa[fu].l.push_back(edge(fv, (*j).second));
}
}
}
for (int i = 0; i < newDfa.size(); ++i)
{
for (auto j = newDfa[i].l.begin(); j != newDfa[i].l.end(); ++j)
{
cout << "S" << i << " S" << (*j).first << " " << (*j).second << endl;
}
}
}

测试数据

输入输出描述

輸入
7 14
0 0 0 1 1 1 1
0 1 a
0 2 b
1 3 a
1 2 b
2 1 a
2 4 b
3 3 a
3 5 b
4 6 a
4 4 b
5 6 a
5 4 b
6 3 a
6 5 b

代表的DFA:

input

理论输出
S0 = { 0 }
S1 = { 3 4 5 6 } end
S2 = { 1 }
S3 = { 2 }
S0 S2 a
S0 S3 b
S1 S1 a
S1 S1 b
S2 S1 a
S2 S3 b
S3 S2 a
S3 S1 b

化简后的DFA:
output