2

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

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

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

在此处输入图像描述

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

这可能是正确的答案吗?

4

2 回答 2

3

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

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

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

正则表达式可视化

调试演示

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

例如以下将起作用:

^(((a*b){2})*)a*$
于 2015-06-20T13:40:48.187 回答
0

这是最好的解决方案,因为我遵循从 DFA 转换为正则表达式的算法(由笔完成):

(a*|ba*b)*

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

于 2015-06-26T16:11:59.407 回答