我有一道练习题需要找出两个公式的补集：
(1) (aa|bb)*
和
(2) (a|b)(aa|bb)(a|b).
我认为两者的补集都是a* | b*，意思是只有a或只有b？
查找正则表达式的补集
4
- sushi
3
2个回答
6
您需要按照通常的步骤进行：
- 将正则表达式转换为NFA。
- 将NFA转换为DFA。对于简单情况，可以直接（手动）从正则表达式转换为DFA。
- 将所有非终态转换为终态，反之亦然。
- 将补充DFA转换为正则表达式。这是一种详细的转换示例
我不会向您展示结果，因为这是一个练习，但我将向您展示第一个公式(aa|bb)*的DFA：
从中，您可以清楚地看到a*或b*将无法给出正确的结果。您永远不会进入Trap状态（在补充正则表达式中变成终态），并且您可能会进入状态2a/2b（在补充正则表达式中变成非终态）。
- nhahtdh
1
你用什么工具制作了这个图表？ - Tim Pietzcker
0
简单地说，(aa+bb)* 将包含诸如 null、aa、aaaa、bb、bbbb、aabb、bbaa 等示例字符串，请注意，所有可以形成的字符串都是偶数长度的，而 a 和 b 可以是任何顺序，因此补集应该包含所有奇数长度的字符串 ((a+b)(a+b))*(a+b)
- arun sharma
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
aba既不符合公式，也不符合您的解决方案，因此它不能是补集。 - Bergi