我的练习单上有一道题是求两个公式的补集
(1) (aa|bb)*
and
(2) (a|b)(aa|bb)(a|b).
我认为两者是互补的a* | b*，仅表示a的或仅b's?
您需要完成通常的程序：
- 将正则表达式转换为 NFA。
- 将 NFA 转换为 DFA。对于简单的情况，很容易直接从正则表达式（手动）转换为 DFA。
- 将所有非终止状态转换为终止状态，反之亦然。
- 将补充 DFA 转换为正则表达式。这是此类转换的一个详细示例 https://stackoverflow.com/questions/13676431/regular-expressions-with-repeated-characters/13677120#13677120
我不会向你展示结果，因为它是练习，但我会向你展示第一个公式的 DFA(aa|bb)*:
从这里你可以清楚地看出a* or b*不会给出正确的结果。你永远不会最终陷入Trap状态（成为补充正则表达式中的终止状态），并且您可能最终处于状态2a/2b（这变成non- 补充正则表达式中的终止状态）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
