找到正则表达式的补语

Question

在我的练习表上有一个问题是找到两个公式的补码

(1) (aa|bb)*

和

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

在我看来a* | b*,两者的补充只意味着只有a或只有b？

Answer 1

你需要通过常规程序:

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

我不会告诉你结果,因为它是运动,但我会告诉你第一个公式的DFA (aa|bb)*:

由此,您可以清楚地看到a*或b*不会给出正确的结果.你将永远不会陷入陷阱状态(它成为补充正则表达式中的终止状态),并且你可能最终处于状态2a/2b(在补充正则表达式中变为非终结状态).