CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Description
对于两个正则表达式 r 和 s，判断这两个正则表达式的关系。正则表达式的关系有 4 种：
- r 和 s 等价，即 r 描述的语言和 s 描述的语言相等；
- r 描述的语言是 s 描述的语言的真子集；
- s 描述的语言是 r 描述的语言的真子集；
- 非上述情况。
输入的正则表达式只包含小写字母a-z, |, *, ?, +, E, (, )。其中，a-z是所描述语言字符集中的字符，E 表示 epsilon（空串），其它符号含义和教材相同。
请编写一个 C++ 程序实现上述功能。
Input
第一行是测试数组的组数 T。
接下来的 T 行，每行是两个正则表达式 r 和 s，每个正则表达式只包含 a-z, |, \*, ?, +, E, (, )。两个正则表达式之间用一个空格隔开。
Output
输出有 T 行。对于每组数据，如果 r 和 s 等价，输出 =；如果 r 是 s 的真子集，输出 <；如果 s 是 r 的真子集，输出 >；非上述情况，输出 !。
实验原理
要判断两个正则表达式的关系，我有如下的思路：
- 正则表达式转成中缀表达式
- 中缀表达式转成后缀表达式
- 后缀表达式转成非确定有限自动机
- 非确定有限自动机转成确定有限自动机
- 判断两个确定有限自动机的关系
flowchart TB
subgraph 正则表达式转成中缀表达式
正则表达式R
正则表达式S
end
subgraph 中缀表达式转成后缀表达式
中缀表达式R
中缀表达式S
end
subgraph 后缀表达式转成非确定有限自动机
后缀表达式R
后缀表达式S
end
subgraph 非确定有限自动机转成确定有限自动机
非确定有限自动机R
非确定有限自动机S
end
subgraph 判断两个确定有限自动机的关系
确定有限自动机R
确定有限自动机S
end
正则表达式R-->中缀表达式R
中缀表达式R-->后缀表达式R
后缀表达式R-->非确定有限自动机R
非确定有限自动机R-->确定有限自动机R
正则表达式S-->中缀表达式S
中缀表达式S-->后缀表达式S
后缀表达式S-->非确定有限自动机S
非确定有限自动机S-->确定有限自动机S
确定有限自动机R--是否包含-->确定有限自动机S
确定有限自动机S--是否包含-->确定有限自动机R
算法的大致流程如上图，接下来我详细介绍每一部分的算法。
正则表达式转成中缀表达式
这一步主要将正则表达式中省略的连接运算符（&，即 cat）加上，方便计算机运算。需要添加 & 的有六种情况：
- 两个字符相连，如
aa - 字符和左括号相连，如
a( - 单目运算符和字符相连，如
*a - 单目运算符和左括号相连，如
*( - 右括号和字符相连，如
)a - 右左括号相连，如
)(
总结起来就是：当第一位是字符、单目运算符或右括号，且第二位为字符或左括号时，需要在他们中间加一个连接运算符。于是很容易得到下面的代码。
string regex_to_infix(string s)
{
for (int i = 0; i + 1 < s.size(); ++i)
if (isalpha(s[i]) || s[i] == '?' || s[i] == '+' || s[i] == '*' || s[i] == ')')
if (isalpha(s[i + 1]) || s[i + 1] == '(')
s.insert(i + 1, "&");
return s;
}
以表达式(a|b)*abb为例，预处理后的表达式为：(a|b)*&a&b&b。要注意，此处运算符的优先级别从高到低依次为：
- 单目运算符
?、+、* - 连接运算符
& - 或运算符
|
中缀表达式转成后缀表达式
之前的实验 里已经做过中缀转后缀的程序了，稍作修改就可以用在本程序中。转换过程中用到一个运算符栈，具体过程如下:
- 如果遇到字符，直接将其输出。
- 如果遇到运算符：
- 遇到左括号
(直接压入栈中； - 遇到右括号
)重复将栈里的运算符弹出直到遇到(，将(弹栈但不输出； - 遇到其他运算符：
- 如果栈为空，直接将运算符压入栈中；
- 如果栈不为空，弹出栈中优先级大于等于当前运算符的运算符并输出，再将当前运算符入栈。
- 遇到左括号
当输入串读取完之后，如果栈不为空，则将栈中元素依次出栈并输出。
string infix_to_suffix(const string &s)
{
string str, stak;
static const unordered_map<char, int> priority{
{'?', 3},
{'+', 3},
{'*', 3},
{'&', 2},
{'|', 1},
{'(', 0}};
for (int i = 0; i < s.size(); ++i)
{
if (isalpha(s[i]))
str.push_back(s[i]);
else if (s[i] == ')')
{
while (stak.back() != '(')
{
str.push_back(stak.back());
stak.pop_back();
}
stak.pop_back();
}
else if (s[i] == '(')
stak.push_back(s[i]);
else
{
while (!stak.empty() && priority.at(stak.back()) >= priority.at(s[i]))
{
str.push_back(stak.back());
stak.pop_back();
}
stak.push_back(s[i]);
}
}
str.insert(str.end(), stak.rbegin(), stak.rend());
return str;
}
后缀表达式转成非确定有限自动机
我认为这一步是本次实验的核心。我设计了一个图结构于存储非确定有限自动机，其包含下述内容：
- 边集
e，其中每条有向边包含- 起点
first - 终点
second - 迁移字符
ch
- 起点
- 点集
v，其中每个顶点包含- 出边表
o，保存每条以当前顶点为起点的边的序号 - 是否为接收状态
isAccepted
- 出边表
- 增加一条边
void add(const Edge &ed);- 当加入边的顶点大小超过当前点集大小的时候会自动扩张
- 计算一个图上顶点集合的闭包
vector<int> closure(vector<int> se) const;- 后续 NFA 转 DFA 时会用到
- 计算一个集合的 a_move
vector<int> a_move(const vector<int> &se, char a) const;- 后续 NFA 转 DFA 时会用到
struct Graph
{
struct Vertex
{
vector<int> o;
int isAccepted;
Vertex() : isAccepted(0), o(0) {}
};
struct Edge
{
int first, second;
char ch;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n = 0) : v(n) {}
void add(const Edge &ed);
vector<int> closure(vector<int> se) const;
vector<int> a_move(const vector<int> &se, char a) const;
};
转换过程中要用到一个保存顶点对的栈。按顺序读取后缀表达式，每次读取一个字符，然后根据读取的不同字符，按照不同策略更新当前的图，详见下文。最后栈顶的顶点对 {fi, se} 就是所得 NFA 的初始状态和唯一接受状态；为方便起见，我又按照如下方式连边：
flowchart LR
0--E-->fi
fi-.->se
se--E-->1
这样所得到的 NFA 一定是以状态 0 作为初始状态，状态 1 作为唯一接收状态。
遇到字符
如果遇到字符（此处用a代替），则在图上新建两个顶点 fi、se，在他们之间连一条迁移字符为 a 的边，如下图所示。
flowchart LR
fi--a-->se
然后将顶点对 {fi, se} 压栈。
int fi = nfa.v.size(),
se = nfa.v.size() + 1;
nfa.add({fi, se, s[i]});
stak.push_back({fi, se});
遇到 *
如果遇到闭包运算符 *，则在图上新建两个顶点 fi、se，从栈中弹出一个顶点对 {fi1, se1}，按照如下方式连边（其中fi1到se1的边已经在之前连过了，无需重连）：
flowchart LR
fi--E-->se
fi--E-->fi1
fi1-.->se1
se1--E-->fi
然后将顶点对 {fi, se} 压栈。
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, se, 'E'});
nfa.add({fi, fi1, 'E'});
nfa.add({se1, fi, 'E'});
遇到 ?
虽然可以直接把正则表达式中 a? 转换成 E|a，但是在前缀表达式转中缀表达式过程中做转换有些复杂，因此这一步放在创建自动机的过程中。
在图上新建两个顶点 fi、se，从栈中弹出一个顶点对 {fi1, se1}，按照如下方式连边（其中fi1到se1的边已经在之前连过了，无需重连）：
flowchart LR
fi--E-->se
fi--E-->fi1
fi1-.->se1
se1--E-->se
然后将顶点对 {fi, se} 压栈。
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, se, 'E'});
nfa.add({fi, fi1, 'E'});
nfa.add({se1, se, 'E'});
遇到 +
虽然可以直接把正则表达式中 a+ 转换成 aa*，但是在前缀表达式转中缀表达式过程中做转换有些复杂，因此这一步放在创建自动机的过程中。
不需要创建新节点，直接从栈中弹出一个顶点对 {fi, se}，按照如下方式连边（其中一条边已经在之前连过了，无需重连）：
flowchart LR
fi-.->se
se--E-->fi
然后将顶点对 {fi, se} 重新压栈。
int fi1 = stak.back().first,
se1 = stak.back().second;
nfa.add({se1, fi1, 'E'});
遇到 &
不需要创建新节点，直接从栈中弹出两个顶点对 {fi1, se1}、{fi2, se2}，按照如下方式连边（其中两条边已经在之前连过了，无需重连）：
flowchart LR
fi1-.->se1
fi2-.->se2
se1--E-->fi2
然后将顶点对 {fi1, se2} 重新压栈。
int fi2 = stak.back().first,
se2 = stak.back().second;
stak.pop_back();
int fi1 = stak.back().first,
se1 = stak.back().second;
stak.back().second = se2;
nfa.add({se1, fi2, 'E'});
遇到 |
在图上新建两个顶点 fi、se，从栈中弹出两个顶点对 {fi1, se1}、{fi2, se2}，按照如下方式连边（其中两条边已经在之前连过了，无需重连）：
flowchart LR
fi1-.->se1
fi2-.->se2
fi--E-->fi1
fi--E-->fi2
se1--E-->se
se2--E-->se
然后将顶点对 {fi, se} 重新压栈。
int fi2 = stak.back().first,
se2 = stak.back().second;
stak.pop_back();
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, fi1, 'E'});
nfa.add({fi, fi2, 'E'});
nfa.add({se1, se, 'E'});
nfa.add({se2, se, 'E'});
非确定有限自动机转成确定有限自动机
此处使用了课本上的算法，其算法如下：
- 一开始
d_state中只有一个状态nfa.closure({0})，且无标记 - 选择
d_state中一个无标记的状态T - 给
T打标记 - 对于每个输入字符
a- 计算
U = nfa.closure(nfa.a_move(se, a)) - 如果
U不在d_state中，将U加入d_state且不打标记 - 建立转移状态
{T, U, a}
- 计算
- 如果
d_state中存在一个无标记的状态返回第二步，否则算法结束
其中，计算闭包和 a_move 均只要在图上遍历一下即可，此处不再详述。
Graph nfa_to_dfa(const Graph &nfa)
{
struct ID : map<vector<int>, int>
{
int ask(const vector<int> &v)
{
if (count(v))
return at(v);
int s = size();
return insert({v, s}), s;
}
} d_state;
Graph dfa;
for (vector<vector<int>> stak(1, nfa.closure({0})); !stak.empty();)
{
vector<int> se = stak.back();
stak.pop_back();
int id = d_state.ask(se);
for (char a = 'a'; a <= 'z'; ++a)
{
vector<int> se2 = nfa.closure(nfa.a_move(se, a));
if (!d_state.count(se2))
stak.push_back(se2);
dfa.add({id, d_state.ask(se2), a});
}
}
for (ID::iterator it = d_state.begin(); it != d_state.end(); ++it)
if (find(it->first.begin(), it->first.end(), 1) != it->first.end())
dfa.v[it->second].isAccepted = 1;
return dfa;
}
判断两个确定有限自动机的关系
这一步才是主要实现实验要求的部分，实际上这里只要实现一个检查「包含」关系的函数即可，然后按照
- 如果 r 包含 s 且 s 包含 r，则 r 和 s 等价
- 如果 r 不包含 s 且 s 包含 r，则 r 描述的语言是 s 描述的语言的真子集
- 如果 r 包含 s 且 s 不包含 r，则 s 描述的语言是 r 描述的语言的真子集
- 非上述情况
得到答案。而要判断有限自动机的包含关系，可以通过一次搜索遍历完成。
int contain(const Graph &lhs, const Graph &rhs)
{
vector<vector<int>> vis(lhs.v.size(), vector<int>(rhs.v.size(), 0));
for (vector<pair<int, int>> q(vis[0][0] = 1, {0, 0}); !q.empty();)
{
int xl = q.back().first,
xr = q.back().second;
q.pop_back();
if (lhs.v[xl].isAccepted < rhs.v[xr].isAccepted)
return 0;
for (int i = 0; i < lhs.v[xl].o.size(); ++i)
{
int yl = lhs.e[lhs.v[xl].o[i]].second,
yr = rhs.e[rhs.v[xr].o[i]].second;
if (!vis[yl][yr])
vis[yl][yr] = 1, q.push_back({yl, yr});
}
}
return 1;
}
这段代码同时经过了 History of Languages 这道题目的测试，可以验证它的正确性！
实验过程
我的实验环境是：
- Intel(R) Core(TM) i7-6567U CPU @3.30GHZ 3.31GHz
- 8.00GB RAM
- Windows 10 2004 19041.264, 64-bit
- Visual Studio Code 1.47.0
- Remote - WSL 0.44.4：配合 WSL，在 Windows 上获得 Linux 接近原生环境的体验。
- Windows Subsystem for Linux [Ubuntu 20.04 LTS]：WSL 是以软件的形式运行在 Windows 下的 Linux 子系统，是近些年微软推出来的新工具，可以在 Windows 系统上原生运行 Linux。
- gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)
- Visual Studio Code 1.47.0
在 Linux 终端依次执行下述指令可以将我的代码 regex_cmp.cpp 编译成可执行文件 regex_cmp。然后运行这个程序并计时，将输入重定向到 input.txt，将输出重定向到 output.txt。
$ g++ -std=c++11 -O3 -o regex_cmp regex_cmp.cpp
$ time ./regex_cmp < input.txt > output.txt
real 0m0.010s
user 0m0.000s
sys 0m0.000s
可以看到，在我的机器上，十组测试数据只花费了十毫秒左右的时间就全部计算完毕，运行效率还是非常高的。
样例输入 input.txt
这里我构造了十组测试数据。前六组测试数据分别用于检验我的程序能不能够正确处理 ?、+、*、&（正则表达式中省略了连接运算符）、|、E（空集）；第七到第十组数据是我构造的复杂一点的例子，其中第十组数据识别的语言也是之前作业写过的「小小语言」（将原字符集中的 / 换成 a）。
10
a a?
a a+
a a*
a ab
a a|b
a* (a|E)*
a(a|b)* a(ab)?+b
a(a|b)* a(ab)*b
a(ab)*b a(a|b)*ab
ao(o*z|a)*o+a aoa*(za*|o)*oa
样例输出 output.txt
容易手动验证这里结果的正确性。
<
<
<
!
<
=
>
>
!
=
测试数据 testdata.in
这组数据是老师提供的，当然我的结果也是正确的。
5
((E|a)b*)* (a|b)*
b*a*b?a* b*a*ba*|b*a*
b*a*b?a* (b*|a*)(b|E)a*
(c|d)*c(c|d)(c|d) (c|d)*d(c|d)(c|d)
x+y+z+ x*y*z*
测试答案 testdata.out
=
=
>
!
<
源代码 regex_cmp.cpp
得益于（自认为）非常不错的数据封装，此处仅用了不到 240 行代码（且未压行）就实现了所有功能！（网上一些实现 仅将正则表达式转成自动机就用了近一千行代码）
#include <bits/stdc++.h>
using namespace std;
struct Graph
{
struct Vertex
{
vector<int> o;
int isAccepted;
Vertex() : isAccepted(0), o(0) {}
};
struct Edge
{
int first, second;
char ch;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n = 0) : v(n) {}
void add(const Edge &ed)
{
if (v.size() < max(ed.first, ed.second) + 1)
v.resize(max(ed.first, ed.second) + 1);
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
vector<int> closure(vector<int> se) const
{
vector<int> vis(v.size(), 0);
while (!se.empty())
{
int u = se.back();
se.pop_back();
vis[u] = 1;
for (int i = 0, k; i < v[u].o.size(); ++i)
if (k = v[u].o[i], !vis[e[k].second] && e[k].ch == 'E')
{
vis[e[k].second] = 1;
se.push_back(e[k].second);
}
}
for (int i = 0; i < vis.size(); ++i)
if (vis[i])
se.push_back(i);
return se;
}
vector<int> a_move(const vector<int> &se, char a) const
{
vector<int> vis(v.size(), 0), ans;
for (int j = 0; j < se.size(); ++j)
for (int u = se[j], i = 0, k; i < v[u].o.size(); ++i)
if (k = v[u].o[i], e[k].ch == a && !vis[e[k].second])
vis[e[k].second] = 1;
for (int i = 0; i < vis.size(); ++i)
if (vis[i])
ans.push_back(i);
return ans;
}
};
string regex_to_infix(string s)
{
for (int i = 0; i + 1 < s.size(); ++i)
if (isalpha(s[i]) || s[i] == '?' || s[i] == '+' || s[i] == '*' || s[i] == ')')
if (isalpha(s[i + 1]) || s[i + 1] == '(')
s.insert(i + 1, "&");
return s;
}
string infix_to_suffix(const string &s)
{
string str, stak;
static const unordered_map<char, int> priority{
{'?', 3},
{'+', 3},
{'*', 3},
{'&', 2},
{'|', 1},
{'(', 0}};
for (int i = 0; i < s.size(); ++i)
{
if (isalpha(s[i]))
str.push_back(s[i]);
else if (s[i] == ')')
{
while (stak.back() != '(')
{
str.push_back(stak.back());
stak.pop_back();
}
stak.pop_back();
}
else if (s[i] == '(')
stak.push_back(s[i]);
else
{
while (!stak.empty() && priority.at(stak.back()) >= priority.at(s[i]))
{
str.push_back(stak.back());
stak.pop_back();
}
stak.push_back(s[i]);
}
}
str.insert(str.end(), stak.rbegin(), stak.rend());
return str;
}
Graph suffix_to_nfa(const string &s)
{
vector<pair<int, int>> stak;
Graph nfa(2);
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '?')
{
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, se, 'E'});
nfa.add({fi, fi1, 'E'});
nfa.add({se1, se, 'E'});
}
else if (s[i] == '+')
{
int fi1 = stak.back().first,
se1 = stak.back().second;
nfa.add({se1, fi1, 'E'});
}
else if (s[i] == '*')
{
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, se, 'E'});
nfa.add({fi, fi1, 'E'});
nfa.add({se1, fi, 'E'});
}
else if (s[i] == '&')
{
int fi2 = stak.back().first,
se2 = stak.back().second;
stak.pop_back();
int fi1 = stak.back().first,
se1 = stak.back().second;
stak.back().second = se2;
nfa.add({se1, fi2, 'E'});
}
else if (s[i] == '|')
{
int fi2 = stak.back().first,
se2 = stak.back().second;
stak.pop_back();
int fi = nfa.v.size(),
se = nfa.v.size() + 1,
fi1 = stak.back().first,
se1 = stak.back().second;
stak.back() = {fi, se};
nfa.add({fi, fi1, 'E'});
nfa.add({fi, fi2, 'E'});
nfa.add({se1, se, 'E'});
nfa.add({se2, se, 'E'});
}
else
{
int fi = nfa.v.size(), se = nfa.v.size() + 1;
nfa.add({fi, se, s[i]});
stak.push_back({fi, se});
}
}
nfa.add({0, stak.back().first, 'E'});
nfa.add({stak.back().second, 1, 'E'});
nfa.v[1].isAccepted = 1;
return nfa;
}
Graph nfa_to_dfa(const Graph &nfa)
{
struct ID : map<vector<int>, int>
{
int ask(const vector<int> &v)
{
if (count(v))
return at(v);
int s = size();
return insert({v, s}), s;
}
} d_state;
Graph dfa;
for (vector<vector<int>> stak(1, nfa.closure({0})); !stak.empty();)
{
vector<int> se = stak.back();
stak.pop_back();
int id = d_state.ask(se);
for (char a = 'a'; a <= 'z'; ++a)
{
vector<int> se2 = nfa.closure(nfa.a_move(se, a));
if (!d_state.count(se2))
stak.push_back(se2);
dfa.add({id, d_state.ask(se2), a});
}
}
for (ID::iterator it = d_state.begin(); it != d_state.end(); ++it)
if (find(it->first.begin(), it->first.end(), 1) != it->first.end())
dfa.v[it->second].isAccepted = 1;
return dfa;
}
int contain(const Graph &lhs, const Graph &rhs)
{
vector<vector<int>> vis(lhs.v.size(), vector<int>(rhs.v.size(), 0));
for (vector<pair<int, int>> q(vis[0][0] = 1, {0, 0}); !q.empty();)
{
int xl = q.back().first,
xr = q.back().second;
q.pop_back();
if (lhs.v[xl].isAccepted < rhs.v[xr].isAccepted)
return 0;
for (int i = 0; i < lhs.v[xl].o.size(); ++i)
{
int yl = lhs.e[lhs.v[xl].o[i]].second,
yr = rhs.e[rhs.v[xr].o[i]].second;
if (!vis[yl][yr])
vis[yl][yr] = 1, q.push_back({yl, yr});
}
}
return 1;
}
int main()
{
int t;
for (cin >> t; t--;)
{
string a, b;
cin >> a >> b;
const Graph
dfa = nfa_to_dfa(suffix_to_nfa(infix_to_suffix(regex_to_infix(a)))),
dfb = nfa_to_dfa(suffix_to_nfa(infix_to_suffix(regex_to_infix(b))));
cout << "!<>="[contain(dfa, dfb) << 1 | contain(dfb, dfa)] << "\n";
}
}