<分区>
假设给定了两个正则表达式字符串:
boost::regex r1 = "[AB]";
boost::regex r2 = "[ABCDEF]";
有没有一种简单的方法可以用 boost::regex 确定 r1 是否是 r2 的子集?
在上面的例子中,r1 是 r2 的子集。
boost::regex_match 使用字符串和正则表达式参数。但是使用两个正则表达式的东西会很好。
此问题仅与 C++ 和 boost::regex 库有关。
<分区>
假设给定了两个正则表达式字符串:
boost::regex r1 = "[AB]";
boost::regex r2 = "[ABCDEF]";
有没有一种简单的方法可以用 boost::regex 确定 r1 是否是 r2 的子集?
在上面的例子中,r1 是 r2 的子集。
boost::regex_match 使用字符串和正则表达式参数。但是使用两个正则表达式的东西会很好。
此问题仅与 C++ 和 boost::regex 库有关。
最佳答案
将正则表达式转换为 DFA 图 g1 和 g2。
将 g1' 和 g2' 定义为相同的接受状态反转的图。
定义 a = g1 x g2' 和 b = g1' x g2,您可以在其中跟踪输入的两组状态。 a 和 b 的接受状态是源-产品图中都接受的状态。
a 接受的字符串是 r1 接受而 r2 不接受的字符串。
b 接受的字符串是 r2 接受而 r1 不接受的字符串。
当且仅当 r1 接受的每个字符串也被 r2 接受时,r1 是 r2 的子集。
所以简单地证明a不接受任何字符串来证明r1是r2的子集。
如果你想要严格的子集,还要证明 b 接受至少一个字符串。
我不知道有什么方法可以通过 boost 轻松完成这些操作。我不知道这些步骤是否符合“简单”的条件。我怀疑不是,因为这个问题是 PSPACE 完备的。
关于c++ - 使用 boost::regex (c++) 比较两个正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45919355/