regex - 包含 a 和偶数个 b 的字符串的正则表达式

Question

如何定义正则表达式以具有以下语言？

L = {w ∈ {a, b}* | w 有偶数个 b }

我试图创建相关的自动机：

从那我尝试应用该算法从 DFA 获得常规 espression，我得到了这个公式：a*ba*b。

这可能是正确的答案吗？

Answer 1

你很接近，但你需要a*在你的模式的末尾。你还需要锚^并$指定字符串的开始和结束。然后你可以将所有的正则表达式放在一个捕获组中，并使用它*来匹配任何偶数，如果b, 和a*0 个b:

 ^((a*ba*ba*)*|a*)$

注意:|是一个逻辑 OR 并使您的正则表达式引擎匹配(a*ba*ba*)*or a*。

调试演示

你也可以让它更优雅，但由于你对正则表达式不太熟悉，所以我建议使用前面的模式。

例如以下将起作用：

^(((a*b){2})*)a*$

Answer 2

这是最好的解决方案，因为我遵循从 DFA 转换为正则表达式的算法（由笔完成）：

(a*|ba*b)*

你可以在这里测试它，你可以通过观看这个视频来了解这个算法。