regex - 如何确定一个正则表达式是否是另一个正则表达式的子集？

Question

给定两个正则表达式，A = 0*1* U 1*0* 和 B = (01 U 10)*，我如何确定一个是否是另一个的子集。我想一种方法是列出一些示例，看看它们是否有任何共同点。在这种情况下，我看到字符串 01、10 在两个集合中共享。所以他们不是彼此的子集？我怎么知道一个正则表达式是另一个正则表达式的子集？一般而言，您如何着手解决此类问题？

Answer 1

显然有很多方法可以做到这一点——任何合乎逻辑的论证都可以构成有效的证明。然而，回答这个问题的一个有启发性的方法是使用算法来计算一般问题的答案。

如果两种语言都包含另一种，则两种语言是等价的。如果一种语言包含另一种语言，则包含语言与包含语言的差异是空集。因此，如果两种语言A和B相等，那么A\B和B\A都是空的；如果 A\B 和 B\A 都为空，则 A 和 B 必须相等。

给定一个正则表达式，至少有一种已知的正确算法可以将其转换为具有 lambda/epsilon 转换的等效 NFA。这种结构被用于正则表达式和有限自动机等价性的规范证明。

给定具有 lambda/epsilon 转换的 NFA，至少有一种已知的正确算法可以将其转换为等效的 DFA。子集构造就是这样一种算法。

给定两个 DFA，至少有一个已知的正确算法可以生成一个 DFA，该 DFA 接受这两个 DFA 接受的语言差异。笛卡尔积机构造就是这样一种算法。

给定一个 DFA，有一个算法可以确定它是否接受空语言。 DFA 最小化然后检查任何接受状态就是这样一种算法。

因此，要通过算法判断两个正则表达式 r1 和 r2 是否相等:

• 为 r1 生成一个 NFA-lambda N1
• 为 r2 生成一个 NFA-lambda N2
• 为 N1 生成 DFA D1
• 为 N2 生成 DFA D2
• 为 L(D1)\L(D2) 生成 DFA D12
• 为 L(D2)\L(D1) 生成 DFA D21
• 通过最小化 D12 生成 DFA M12
• 通过最小化 D21 生成 DFA M21
• L(r1) = L(r2) 当且仅当 M12 和 M21 都接受空语言

当它有疑问时，解决它