如果这篇博客帮助到你,可以请我喝一杯咖啡~
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";
}
}