regex - 查找正则表达式的补码

Question

我的练习单上有一个问题要找到两个公式的补集

(1)(aa|bb)*

和

(2) (a|b)(aa|bb)(a|b)。

在我看来，两者的补充是a* | b*指只有a's 还是 only b's？

Answer 1

您需要通过通常的程序：

• 将正则表达式转换为 NFA。
• 将 NFA 转换为 DFA。对于简单的情况，很容易（手动）从正则表达式直接转换为 DFA。
• 将所有非终端状态转换为终端状态，反之亦然。
• 将补充 DFA 转换为正则表达式。这是这种转换的一个详细示例

我不会向您展示结果，因为它是练习，但我会向您展示第一个公式的 DFA (aa|bb)*：

由此，您可以清楚地看到a*或b*不会给出正确的结果。您永远不会处于Trap状态（在补充正则表达式中成为终止状态），并且您可能最终处于状态2a/2b（在补充正则表达式中成为非终止状态）。

Answer 2

简单地说 (aa+bb)* 将包含示例字符串，例如 null、aa、aaaa、bb、bbbb、aabb、bbaa 等等，所以补码应该包含所有奇数长度的字符串 ((a+b)(a+b))*(a+b)